学步园

O(n) 算法，整理一下。发现输入还有点问题。以后有空改。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

#define N 1000000
char a[N];
int p[N]; // 例：若 p[13] = 4 说明 13 - (4 - 1) 到 13 + (4 - 1) 的 a[] 是回文串

int main()
{
	a[0] = '$';
	a[1] = '#';
	for (; a[2] = getchar(); )
	{
		a[3] = '#';
		for (int i = 4; ; i += 2)
		{
			a[i] = getchar();
			if (a[i] == '\n')break;
			a[i + 1] = '#';
		}
		int l = strlen(a);

		int ir, mr = 0;
		// mr是每个i以前所以回文串中最靠右的位置，ir是这个串的中间位置

		for (int i = 1; i < l; i++)
		{
			if (mr > i) p[i] = min (mr - i, p[2 * ir - i]);
			else p[i] = 1;
			for (; a[i + p[i]] == a[i - p[i]]; p[i]++) ;
			if (i + p[i] > mr)
        mr = i + p[i], ir = i;
		}
		int maxlen = 0, position;
		for (int i = 1; i < l; i++)
			if(p[i] > maxlen)
        maxlen = p[i], position = i;
		maxlen--; // 这时 maxlen 是原来字符串中最长回文子串长度
		printf("%d\n", maxlen);

		for (int i = position - maxlen; i <= position + maxlen; i++)
			if (a[i] != '#')
        printf ("%c", a[i]);
		putchar ('\n');
		memset (p, 0, sizeof(p));
		memset (a, 0, sizeof(a));
		a[0] = '$';
		a[1] = '#';
	}
	return 0;
}