algorithm Study/2014/koi_virus

#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";

}