[백준/BOJ] 백준 1701번 : Cubeditor

www.acmicpc.net/problem/1701

1701번: Cubeditor

KMP알고리즘의 pi를 이용해서 문제를 해결하였다.

 

코드

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

//알고리즘 문제해결 전략2 책 KMP 알고리즘 공부 실습
//KMP알고리즘의 pi를 이용해서 문제를 해결
int n;
string input;

int Solve(string check_string)
{
	vector<int> pi(5000, 0);

	int max_pi = 0;
	int start = 1;
	int matched = 0;
	int check_string_size = check_string.size();

	while (start + matched < check_string_size)
	{
		if (check_string[start + matched] == check_string[matched])
		{
			matched++;
			pi[start + matched - 1] = matched;
			max_pi = max(max_pi, pi[start + matched - 1]);
		}

		else
		{
			if (matched == 0)
			{
				start++;
				matched = 0;
			}

			else
			{
				start += matched - pi[matched - 1];
				matched = pi[matched - 1];
			}
		}
	}

	return max_pi;
}

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

	cin >> input;

	n = input.size();

	int result = 0;
	for (int i = 0; i < n; i++)
	{
		string temp_input = input.substr(i, n - i);
		result = max(Solve(temp_input), result);
	}

	cout << result;

	return 0;
}