BOJ 1701 - Cubeeditor (KMP, 실패함수)

https://www.acmicpc.net/problem/1701

 

입력된 문자열에서 두 번 이상 나오는 부분 문자열의 길이중 최대를 출력하는 문제.

 

 abcabcabc 가 주어졌을 때, abc와 abcabc모두 가능하므로 둘 중 더 긴 abcabc의 길이인 6이 정답이다.

 

두 번 이상 나오는 부분 문자열의 길이 중 최대 -> 모든 부분 문자열 중에서 실패함수의 최대값

fail[n-1]까지 구하면서 인덱스0~1, 0~2, 0~3, ... 0~n-1 부분 문자열 중 실패함수를 모두 구할 수 있다.

따라서 시작지점이 0일때, 1일때, .... n-2일 때의 실패함수를 모두 확인해서 최대값을 출력하면 된다.

 

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
const int MAX = 5005;

int main() {
	string str; cin >> str;

	int mx = 0;
	for (int p = 0; p < str.size(); p++) {
		int fail[MAX] = { 0 };
		for (int i = 1,j=0; i < str.size()-p; i++) {
			while (j > 0 && str[p + i] != str[p+j])
				j = fail[j - 1];
			if (str[p + i] == str[p+j]) {
				fail[i] = ++j;
				mx = max(mx, fail[i]);
			}
		}
	}
	cout << mx << '\n';
}