LightOJ 1258 Making Huge Palindromes（KMP）

题意

给定一个字符串 (S) ，一次操作可以在这个字符串的右边增加任意一个字符。求操作之后的最短字符串，满足操作结束后的字符串是回文。

(1 leq |S| leq 10^6)

思路

( ext{KMP}) 的 (fail) 数组是整个算法最重要的东西，能拓展出很多东西。

对于一个模式串（pattern）(P) ，(fail) 数组为 (f) ，那么 (f[i]) 就是如果匹配到 (i) 这个位置失配，下次去尝试的位置，也就说明了从字符串头到 (f[i]-1) 这一段，在 (i-1) 位置以左有一段相同的串。这是对 (fail) 数组的一种理解，想要更深入的理解，最好的方法就是做题。

本题等价于在 (S) 左边删去任意字符使剩下的字符串回文，只需求出字符串 (S) 从右开始能得到最长的回文串长度即可。设模式串为 (S) 的反字符串 (P)，回文串长度就是 (S) 在最右端能匹配 (P) 的最长长度。

代码

#include<bits/stdc++.h>
#define FOR(i,x,y) for(int i=(x),i##END=(y);i<=i##END;++i)
#define DOR(i,x,y) for(int i=(x),i##END=(y);i>=i##END;--i)
typedef long long LL;
using namespace std;
const int N=1e6+5;
char T[N],P[N];
int n,f[N];

int main()
{
	int Case;
	scanf("%d",&Case);
	FOR(cas,1,Case)
	{
		scanf("%s",T);
		n=strlen(T);
		FOR(i,0,n-1)P[i]=T[n-i-1];
		P[n]=' ';
		f[0]=f[1]=0;
		FOR(i,1,n-1)
		{
			int j=f[i];
			while(j&&P[i]!=P[j])j=f[j];
			f[i+1]=j+(P[i]==P[j]);
		}
		int j=0;
		FOR(i,0,n-1)
		{
			while(j&&T[i]!=P[j])j=f[j];
			if(T[i]==P[j])j++;
			if(i==n-1)printf("Case %d: %d
",cas,n+(n-j));
		}
	}
	return 0;
}