[백준 1701] Cubeditor

문제 링크 => 1701번: Cubeditor (acmicpc.net)

1701번: Cubeditor

---

KMP 를 이용하는 문제이다.

 

임의의 문자열 S = "baacaa" 가 있다고 가정하자.

 

KMP Table 를 다음과 같은 과정으로 만들도록 한다.

 

"baacaa" => [ 0, 0, 0, 0, 0, 0 ]

"aacaa" => [ 0, 1, 0, 1, 2 ]

"acaa" => [ 0, 0, 1, 0 ]

"caa" => [ 0, 0, 0 ]

"aa" => [ 0, 1 ]

"a" => [ 0 ]

 

여기서 정답은 Table 를 만들는 과정속에서 얻어진 value 의 Maximum 이다.

 

풀이 code

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int f(string s) {
	if (s.size() == 1) return 0;
	vector<int> table(s.size(), 0);
	int cnt = 0, j = 0;
	for (int i = 1; i < s.size(); i++) {
		while (j > 0 && s[i] != s[j]) j = table[j - 1];
		if (s[i] == s[j]) {
			table[i] = ++j;
			cnt = max(cnt, j);
		}
	}

	return cnt;
}

string getS(string s, int idx) {
	string ret = "";
	for (int i = idx; i < s.size(); i++) {
		ret += s[i];
	}
	return ret;
}

void solve() {

	string s;
	cin >> s;

	int cnt = 0;
	for (int i = 0; i < s.size(); i++) {
		cnt = max(cnt, f(getS(s,i)));
	}

	cout << cnt;
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	solve();

	return 0;
}