kmp. [7575]

[1. 문제 설명]

https://www.acmicpc.net/problem/7575

---

[2. 풀이 접근]

임의의 프로그램에 대해서, 발생 할 수 있는 K 개의 모든 코드를 구하고,

이 코드를 나머지 프로그램에서 찾는다.

• 문제에서는 코드 길이가 K 이상인 경우에도 바이러스라고 판정가능하다 하였는데,
• 사실 K 개만 일치하면, K개 보다 큰 경우에 대해서 코드 일치 여부와 관계 없이
• 바이러스 코드로 추정 할 수 있다.
  # K+1 개, 일치 => K 개가 일치하므로 상관 없다.
  # K+1 개. 불일치 => 역시 K 개는 일치하므로 상관 없다.
• 일종의 함정인 셈 
  # K=4 라고 하면,
  # K=5 코드, K=6 코드를 구할 필요가 없다. 

연산 횟수를 대강 계산하면,

1. 생성할 수 있는 코드 개수 : 1000개 (정확하게는 최대 996 개)
2. 나머지 프로그램 개수: 100개 (정확하게는 최대 999개)
3. 한 프로그램 당 정수 개수 : 1000개
4. 전부 곱하면, 100,000,000 개

숫자가 좀 커서 시간초과가 발생할 것 같았으나,

테스트 머신의 cpu clock 이 1Ghz 라 가정하고,

1초의 0.5G 의 연산이 가능하다 생각하면, 대강 1억번의 연산은 1초안에 수행이 가능하다 볼 수 있다.(?)

• ??

고찰

• 최대 1억번의 연산은 1초 안에 해결 가능한 걸로 여기도록 한다.
• 플로이드-워셜 알고리즘의 경우 그 수행 횟수를 생각해보도록 한다.
• 최초 코드의 kmpSearch 에서, find 한 경우 이 때, begin 을 반환하도록 하였는데,
• 0번째 위치에서 m 개가 일치 할 수 있으므로, 이렇게 반환하는 것은 위험하다...

---

[3. 코드]