[C++] Cubeditor(KMP) - 1701

KMP 알고리즘

---

위 문제는 KMP 알고리즘에서

pattern table 만드는 것만 알면 풀 수 있는 아주 간단한 문제 입니다.

 

두번 이상 검색되는 패턴중에 가장 긴 패턴의 길이를 구하는 것인데

pattern table 생성하는 과정에서 가장긴 접미사를 가진 애만 찾으면 해결되는 문제입니다.

 

 

int KMP(string str)
{
	vector<int> table(str.size());
	for (int head = 0, tail = 1; tail < str.size(); tail++)
	{
		while (head > 0 && str[head] != str[tail])
			head = table[head - 1];

		if (str[head] == str[tail])
			table[tail] = ++head;
	}

	int MAX = 0;
	for (int i = 0; i < str.size(); i++)
		if (MAX < table[i]) MAX = table[i];

	return MAX; // 테이블에 저장된 값 중에서 가장 큰 값을 리턴
}

 

 

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

	int MAX = 0;
	for (int i = 0; i < str.size(); i++)
	{
		// 맨 앞의 문자 하나씩 때어서
		// 여러 경우에서의 패턴 테이블을 만듬
		int n = KMP(str.substr(i, str.size() - i));
		if (MAX < n) MAX = n;
	}
	cout << MAX;
	return 0;
}