백준 1701 Cubeditor

KMP알고리즘을 수행할 때 pi를 구한다.

그런데 만약 pattern에 2번 이상 반복되는 부분 문자열이 있다면 pi에 그 부분문자열의 길이가 기록 된다.

예를들어 pattern이 aabcaa라고 하자.

그렇다면 index가 6일때 접두사와 접미사가 같은 부분이 나오고, pi[6] = 2로 기록된다.

그런데 이 값은 접두사와 접미사가 같은 부분의 길이를 의미하기도 한다. 

따라서 pi[6]의 값은 pi[0~6]의 최대 길이 중복 부분 문자열의 길이(우리가 구하고 싶은 값)가 된다.

또 다른 예로 pattern을 aabcaabxx라고 하자.

이 패턴에서는 index가 6일때 마찬가지로 접두사와 접미사가 같은 부분이 나오고, index가 7일때 또 한번 나온다. (pi[6] = 2, pi[7] = 3)

따라서 pi의 최대값을 체크하면 pattern에서 중복되는 부분문자열의 최대 길이를 알수 있게 된다.

마지막으로 pattern을 caabaac라고 하자. 

이 패턴에서는 pattern[1~5]의 부분문자열에서 aa라는 중복되는 부분문자열이 나온다.

이러한 패턴도 파악하기 위해 우리는 pattern[0~pattern.length]뿐만 아니라, pattern[k~pattern.length], k=0~pattern.length에 대해 

pi를 모두 구한 뒤 최대값을 구할 것이다.

//deque.tistory.com

#include <iostream> 
#include <string> 

using namespace std;

int pi[5002][5002];

int main() {
	string str;
	cin >> str;
	int strlength = str.size();
	int max = 0;
	for (int k = 0; k < strlength; k++) { //pi[k][i]는 str[k]~str[-1]를 pattern이라고 했을때의 pi이다
		string pattern = str.substr(k, strlength);
		int j = 0;
		for (int i = 1; i < pattern.size(); i++) {
			while (j > 0 && pattern[i] != pattern[j]) {
				j = pi[k][j - 1];
			}
			if (pattern[i] == pattern[j]) {
				j++;
				pi[k][i] = j;
			}
		}
		for (int i = 0; i < pattern.size(); i++) {
			if (pi[k][i] > max) max = pi[k][i];
		}
	}

	cout << max << endl;

	return 0;
}