AlgorithmStudy/2014/koi virus

문제

• [1]

권영기

사용 언어

• 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++로 구현하니까 시간 안에 잘 나옴. ㅠㅠ

코드

#include<iostream>
#include<memory.h>
using namespace std;
int n, k;
int pi[1020];
int program[120][1020];
int program_size[120];
int virus_candidate[2020][1020];
bool answer = true;
bool virus_check[2020];
int find_pi(int p){
	int i = 0, j = -1;
	pi[0] = -1;
	while(i < k){
		if(j == -1 || virus_candidate[p][i] == virus_candidate[p][j]){
			i++;
			j++;
			pi[i] = j;
		}
		else{
			j = pi[j];
		}
	}
        return 0;
}
bool kmp(int s, int p){
	int i = 0, j = -1;
	memset(pi, 0, sizeof(int) * 1020);
	find_pi(p);
	while(i < program_size[s]){
		if(j == -1 || program[s][i] == virus_candidate[p][j]){
			i++;
			j++;
		}
		else{
			j = pi[j];
		}
		if(j == k){
			return true;
			j = pi[j];
		}
	}
	return false;
}
int main(void)
{
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);

	cin>>n>>k;
	for(int i = 0; i<n; i++){
		cin>>program_size[i];
		for(int j = 0; j<program_size[i]; j++){
			cin>>program[i][j];
		}
	}
	int count = 0;
	for(int i = 0; i<program_size[0] - k + 2; i++){
		for(int j = 0; j<k; j++){
			virus_candidate[count][j] = program[0][i + j];
			virus_candidate[count + 1][j] = program[0][i + k - j - 1];
		}
		count += 2;
	}
	
	int m = count;
	for(int i = 1; i<n; i++){
		for(int j = 0; j<m; j+=2){
			if(!virus_check[j] && !kmp(i, j) && !kmp(i, j + 1)){
				virus_check[j] = virus_check[j+1] = true;
				count -= 2;
			}
		}
		if(count == 0){
			answer = false;
			break;
		}
	}

	if(answer)cout<<"YES";
	else cout<<"NO";

}