[백준 1701] Cubeditor (C++)

문제 링크: https://www.acmicpc.net/problem/1701

1701번: Cubeditor

1. 주의할 점

- KMP 알고리즘에 대해 알고 있어야 한다

 

 

 

2. 구현

- Substr함수를 통해 입력 받은 문자의 부분문자열을 구한다

- GetPi() 함수를 통해 부분문자열의 일치하는 접두사와 접미사의 최대 길이를 구한다

- 일치하는 부분 문자열의 최대 길이 -> GetPi() 함수를 통해 구한 Pi에서의 최대값

 

#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;
}