백준 1701번 Cubeditor

문제

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

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

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

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

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

입력

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

출력

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

 

2번이상 나오는 부분 문자열 구하기위해 2중포문으로 모든 부분문자열을 긴 것부터 짧은 순으로 만들어서 

KMP를 통해 구하고 그 길이 반환했는데 시간초과.....

 

그렇다면 시간을 줄이기 위해 어떻게 해야 할까...?

abcdabcabb 이런 스트링이 있다고 했을 때, 나올수 있는 부분 문자열은

abcdabcabb abcdabcab abc abcd bcda bcdabc ..... 무수히 많다.

이 부분 문자열들이 2번이상 나온다는 것은 

부분문자열 안에 접두사 접미사가 일치하는 부분문자열이 존재하는 것으로 확인 가능

이를테면 bc라는 부분문자열이 저 전체에서 2번이상 반복되는가를 구하는 것은

bcdabcab라는 부분문자열이 bc를 포함하고 있으므로 저 안에서 중간의 bc 2크기를 가지는 것이 확인됨

즉 전체 문자열의 각인덱스에서 시작해서 만드는 전체 부분문자열은 그 갯수가 그렇게 많지 않음

전체 길이가 5000이라면 최대 5000개뿐 , 그중 table을 통해 얻는 접두사 접미사 일치 문자열에 대한 정보로 

모든 케이스에서 가장 긴 값을 선택하면 됨.

#include<iostream>
#include<string>
#include<vector>
using namespace std;
string str;
int maxa;
vector<int> makeTable(string str)
{
	int size = str.size();
	vector<int> table(size, 0);

	int j = 0;
	for (int i = 1; i < size; i++)
	{
		while (j > 0 && str[j] != str[i])
		{
			j = table[j - 1];
		}
		if (str[j] == str[i])
		{
			table[i] = ++j;
		}
	}
	return table;
}

int main(void)
{
	cin >> str;
	int size = str.size();
	maxa = 0;
	int res = 0;
	for (int i = 0 ; i < size; i++)
	{
		string temp = str.substr(i, size);
		vector<int> table = makeTable(temp);
		int maxa = 0;
		for (int j = 0; j < table.size(); j++)
		{
			if (maxa < table[j])
			{
				maxa = table[j];
			}
		}

		if (res < maxa)
		{
			res = maxa;
		}
	}
	cout << res << endl;
}