[BOJ] 7575 : 바이러스

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

---

KMP 문자열 문자열찾기

 N개의 프로그램에서 K개 이상의 공통된 부분 수열을 찾는 문제로 K개의 공통된 부분 수열을 찾으면 되는 문제 입니다.

● 첫 번째 프로그램의 코드에서 K개 씩 가능한 모든 경우의 수를 뽑고, 나머지 프로그램에서 KMP 알고리즘을 이용해서 공통된 부분 수열이 있는지 없는지 찾으면 됩니다.

● 이때, J번 째 프로그램에서 KMP 알고리즘을 이용해 찾아보고, revserse 함수를 이용해 J번 째 프로그램의 코드를 뒤집은 뒤 KMP 알고리즘을 한 번 더 이용해 찾아봐야한다.

예시

K = 4

-1번 프로그램 { 10 8 23 93 21 42 52 22 13 1 2 3 4 }

-2번 프로그램 { 1 3 8 9 21 42 52 22 13 41 42 }

-3번 프로그램 { 9 21 42 52 13 22 52 42 12 21 }

1) 1번 프로그램에서 { 10 8 23 93 } 을 가지고 와서 2, 3번 프로그램에 KMP 진행

2) 1번 프로그램에서 { 8 23 93 21 } 을 가지고 와서 2, 3번 프로그램에 KMP 진행

같은 과정을 반복합니다.

6) 1번 프로그램에서 {42 52 22 13 } 을 가지고 와서 2, 3번 프로그램에서 KMP 진행

--> 2번 프로그램에서는 { 42 52 22 13 } 를 찾을 수 있고, 3번 프로그램에서는 revsere를 진행한 후에 { 42 52 22 13 } 을 찾을 수 있다. 

#include<iostream>
#include<vector>

using namespace std;

vector<int> getPartialMatch(vector<int> N) {
	int m = N.size();
	vector<int> pi(m, 0);
	int begin = 1, matched = 0;
	while (begin + matched < m) {
		if (N[begin + matched] == N[matched]) {
			matched++;
			pi[begin + matched - 1] = matched;
		}
		else {
			if (matched == 0) begin++;
			else {
				begin += matched - pi[matched - 1];
				matched = pi[matched - 1];
			}
		}
	}
	return pi;
}

bool kmp(vector<int> H, vector<int> N) {
	int n = H.size(), m = N.size();
	vector<int> ans;
	vector<int> pi = getPartialMatch(N);
	int begin = 0, matched = 0;
	while (begin + m <= n) {
		if (matched < m && H[begin + matched] == N[matched]) {
			matched++;
			if (matched == m) // 끝까지 다 일치했습니다.
				return true;
		}
		else {
			if (matched == 0) begin++; // 일치한 부분이 하나도 없음 -> 시작포인트를 한 칸 앞으로
			else {
				begin += matched - pi[matched - 1]; // pi 배열을 이용해 다음 시작 지점으로 점프
				matched = pi[matched - 1]; // pi 배열을 이용해 이미 일치하는 부분을 건너뛰고 탐색 시작
			}
		}
	}
	return false;
}

int main(void) {
	int N, K;
	int length[100];
	vector<int> programs[100];
	cin >> N >> K;
	for (int i = 0; i < N; i++) {
		cin >> length[i];
		vector<int> t(length[i]);
		for (int j = 0; j < length[i]; j++) {
			cin >> t[j];
			programs[i] = t;
		}
	}
	bool ans = false;
	for (int i = 0; i < length[0] - K + 1; i++) {
		vector<int> n(K);
		for (int j = 0; j < K; j++)
			n[j] = programs[0][i + j];
		bool checked[100] = {};
		for (int j = 1; j < N; j++)
			checked[j] = kmp(programs[j], n);
		for (int j = 1; j < N; j++) {
			if (checked[j]) continue; 
			reverse(programs[j].begin(), programs[j].end());
			checked[j] = kmp(programs[j], n);
		}

		bool isVirused = true;
		for (int j = 1; j < N; j++)
			if (checked[j] == false) {
				isVirused = false;
				break;
			}
		if (isVirused) {
			ans = true;
			break;
		}
	}
	if (ans) cout << "YES\n";
	else cout << "NO\n";

	return 0;
}

---