백준 1701 Cubeditor

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

1701번: Cubeditor

 

KMP 알고리즘...? 을 활용하는 문제다. 시작점을 하나씩 옮겨가면서 failed 배열을 채운다

이 failed 배열은 보통 'pi' 로 표현하는 그 배열이다.

 

이 배열에서 가장 큰 값이, 가장 긴 문자열의 길이라는 걸 활용하면 문제를 풀 수 있다. 

 

/* Cubeditor */

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

void input();
void solve();

int fail(string , vector<int> &);

string s;

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	input();
	solve();
	return 0;
}

void input() {
	cin >> s;
}

void solve() {

	int res = 0;
	for (int i = 0; i < s.length(); i++) {
		string anti = s.substr(i);
		vector<int> failed(anti.length(), 0);
		res = max(res, fail(anti, failed));
	}

	cout << res << '\n';
}

// aabab
int fail(string p, vector<int> & failed) {
	int j = 0, res = 0;
	for (int i = 1; i < p.length(); i++) {
		while (j > 0 && p[j] != p[i])
			j = failed[j-1];

		if (p[i] == p[j]) {
			failed[i] = ++j;
			res = max(res, j);
		}
	}
	return res;
}