Manacher算法

#include<bits/stdc++.h>
using namespace std;

const int N = 1e4 + 10;
int p[N];
void manacher(string s,int &st,int &x)
{
	memset(p,0,sizeof(p));
	string fn;
	fn += '$';
	int len = s.length();
	for(int i = 0;i < len;i++)
	{
		fn += '#';
		fn += s[i];
	}
	fn += '#';
	cout << s << endl << fn << endl;

	int id = 0,mx = 0;
	len = fn.length();
	for(int i = 1;i < len;i++)
	{
		if(i < mx) p[i] = min(mx - i,p[2*id - i]);
		else p[i] = 1;

		while(i + p[i] < len && fn[i-p[i]] == fn[i + p[i]]) p[i]++;

		if(mx < p[i] + i)
		{
			id = i;
			mx = i + p[i];
		}
		if(x < p[i])
		{
			x = p[i];
			st = i;
		}
	}

	for(int i = 0;i < len;i++)
	cout << fn[i] << " ";
	puts("");
	for(int i = 0;i < len;i++)
	cout << p[i] << " ";
	puts("");
}

int main()
{
	string s;
	while(cin >> s)
	{
		int st,len = 0;
		manacher(s,st,len);
		len--;
		st /= 2;
		st -= 1;
		st -= (len/2);
		int up = st + len;
		cout << st << " " << len << endl;
		for(int i = st;i < up;i++)
		cout << s[i];
		cout << endl;
	}
	return 0;
}