[[TableOfContents]]
== 문제 ==
 * [http://183.106.113.109/pool/koi_virus/koi_virus.php?pname=koi_virus]

== 권영기 ==
=== 사용 언어 ===
 * C++
=== 아이디어 ===
 * 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)
=== 풀다가 겪은 문제 ===
 * 처음에는 Python으로 구현하였음. 근데 자꾸 시간 초과 나옴. 그러나 데이터 규모를 생각하면 시간초과가 나올만한 규모는 아님. 언어적 특성을 파악하지 못해서 생긴 결과물로 예상하고 있음. 한 시간은 날린듯 :(
 * 같은 아이디어로 C++로 구현하니까 시간 안에 잘 나옴. ㅠㅠ
=== 코드 ===