알고리즘 과제 3

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int failure(int n, string P, vector<int> F);

int main()
{
	vector<int> ans;
	string input;
	cin >> input;
	int n = input.length();
	ans.push_back(0);
	for (int i = 1; i < n; i++)
	{
		ans.push_back(failure(i, input, ans));
	}
	for (int i = 0; i < n; i++)
	{
		cout << ans[i] << " ";
	}
	return 0;
}


int failure(int n, string P, vector<int> F)
{
	string tmp;
	int half;
	int ans = 0;
	for (int i = 0; i <= n; i++)
	{
		tmp.insert(tmp.end(), P[i]);
	}
	int len = tmp.length();
	if (len % 2 == 0)
	{
		half = len / 2;
	}
	else
	{
		half = len / 2 + 1;
	}
	for (int i = 0; i < half; i++)
	{
		string prefix;
		string suffix;
		for (int j = 0; j <= i; j++)
		{
			prefix.insert(prefix.end(), tmp[j]);
			suffix.insert(suffix.begin(), tmp[len - j -1]);
		} 
		if (ans < i + 1 && suffix == prefix)
		{
			ans = i + 1;
		}
	}
	return ans;
}