题目链接
题意：
给你一个字符串，在字符串尾部加上一些字符，使这个字符串变成一个回文串（正反读都一样的字符串），求该回文串的最小长度。
思路：
在light oj里这个题目是属于KMP分类的，但乍看好像不是kmp，因为只有一个字符串。要想的到一个回文串，把该字符串翻转接到原串后面必然是一个回文串，但并不一定是最短的。我们必须考虑怎么把两个串尽量融合在一起，这就要看翻转串的前段与原串的后段有多少是匹配的了，这里就用到了KMP算法。
代码：
//2013-05-13-20.01 #include <stdio.h> #include <string.h> const int maxn = 1000005; char a[maxn]; char b[maxn]; int f[maxn]; void getfail() { int l = strlen(b); f[0] = 0; f[1] = 0; for (int i = 1; i < l; i++) { int j = f[i]; while (j && b[i] != b[j]) j = f[j]; if (b[i] == b[j]) f[i+1] = j+1; else f[i+1] = 0; } } int getans() { int la = strlen(a); int lb = strlen(b); getfail(); int j = 0; for (int i = 0; i < la; i++) { while (j && a[i] != b[j]) j = f[j]; if (b[j] == a[i]) j++; } return la + lb - j; } int main() { int t; scanf("%d", &t); for (int i = 1; i <= t; i++) { scanf("%s", a); int l = strlen(a); for (int j = 0; j < l; j++) { b[l-j-1] = a[j]; } b[l] = '\0'; printf("Case %d: %d\n", i, getans()); } return 0; }
