algorithmStudy/2014/koi_virus (rev. 1.6)
- KMP Algorithm
- KMP Algorithm은 문자열 검색 알고리즘이다. 문자열의 길이가 s, 검색하려는 패턴의 길이가 p일때, 시간복잡도가 O(s + p)밖에 안 나오는 엄청 좋은 알고리즘임. Brute-Force로 찾을 때, O(sp)가 나오는 것을 고려해보면 엄청나게 빠름.
- Virus라면, 모든 모든 프로그램에 존재할 것이다. Virus가 아니라면 적어도 한 프로그램에는 존재하지 않을 것이다.
- 한 Program에서 길이 k의 sub-Pattern을 전부 구해놓는다. 이 것들은 virus의 후보가 된다.
- 각 패턴(후보 안에 있는)을 KMP Algorithm을 통해서 모든 프로그램에 검색해보면 된다. 검색해서 존재하지 않으면, 프로그램에서 제외한다.
- 이런 식으로 모든 프로그램을 검색했을 때, 후보에 속한 패턴이 아무 것도 없다면 NO 아니면 YES
- 시간 복잡도는 O(NM^2)
2.3. 풀다가 겪은 문제 ¶
- 처음에는 Python으로 구현하였음. 근데 자꾸 시간 초과 나옴. 그러나 데이터 규모를 생각하면 시간초과가 나올만한 규모는 아님. 언어적 특성을 파악하지 못해서 생긴 결과물로 예상하고 있음. 한 시간은 날린듯
- 같은 아이디어로 C++로 구현하니까 시간 안에 잘 나옴. ㅠㅠ
