백준 1701 Cubeditor

Cubeditor

0.5 초

128 MB

5904

1850

1371

33.793%

문제

Cubelover는 프로그래밍 언어 Whitespace의 코딩을 도와주는 언어인 Cubelang을 만들었다. Cubelang을 이용해 코딩을 하다보니, 점점 이 언어에 맞는 새로운 에디터가 필요하게 되었다. 오랜 시간 고생한 끝에 새로운 에디터를 만들게 되었고, 그 에디터의 이름은 Cubeditor이다.

텍스트 에디터는 찾기 기능을 지원한다. 대부분의 에디터는 찾으려고 하는 문자열이 단 한 번만 나와도 찾는다. Cubelover는 이 기능은 Cubelang에 부적합하다고 생각했다. Cubelang에서 필요한 기능은 어떤 문자열 내에서 부분 문자열이 두 번 이상 나오는 문자열을 찾는 기능이다. 이때, 두 부분 문자열은 겹쳐도 된다.

예를 들어, abcdabc에서 abc는 두 번 나오기 때문에 검색이 가능하지만, abcd는 한 번 나오기 때문에 검색이 되지를 않는다.

이렇게 어떤 문자열에서 두 번 이상 나오는 부분 문자열은 매우 많을 수도 있다. 이러한 부분 문자열 중에서 가장 길이가 긴 것을 구하는 프로그램을 작성하시오.

예를 들어, abcabcabc에서 abc는 세 번 나오기 때문에 검색할 수 있다. 또, abcabc도 두 번 나오기 때문에 검색할 수 있다. 하지만, abcabca는 한 번 나오기 때문에 검색할 수 없다. 따라서, 두 번 이상 나오는 부분 문자열 중에서 가장 긴 것은 abcabc이기 때문에, 이 문자열이 답이 된다.

입력

첫째 줄에 문자열이 주어진다. 문자열의 길이는 최대 5,000이고, 문자열은 모두 소문자로만 이루어져 있다.

출력

입력에서 주어진 문자열의 두 번이상 나오는 부분문자열 중에서 가장 긴 길이를 출력한다.

---

앞선 두 문제보다 살짝 당황스러웠다 문자열이 두번 나와야만 찾을 수 있다는 조건 때문이었는데 사실 바보같은 고민이었다. 그냥 자기 자신을 제외한 부분을 검사하면 되는 거였는데 간과했다 ㅎㅎ..
자기 자신을 제외하고 접두사 === 접미사인 부분문자열집합중 최대 길이의 것을 찾으면 되는 문제이다.

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;

int getPi(string ptn) {
	int len = ptn.size();
	vector<int> pi(len, 0);
	int j = 0;
	for (int i = 1; i < len; i++) {
		while (j > 0 && ptn[i] != ptn[j]) {
			j = pi[j - 1];
		}
		if (ptn[i] == ptn[j]) 
			pi[i] = ++j;		
	}
	sort(pi.begin(), pi.end());
	return pi[len - 1];
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	string str;
	int maxi = 0;
	cin >> str;
	for (int i = 0; i < str.size(); i++) {
		string ptn = str.substr(i, str.size());
		int result = getPi(ptn);
		maxi = max(maxi, result);
	}
	cout << maxi;
	system("pause");
	return 0;
}