题目链接：http://lightoj.com/volume_showproblem.php?problem=1258
就是求逆串和原串的匹配长度
答案就是原串长度的2倍减去匹配长度即可
第一次我将原串接在逆串后面然后一次求失败函数得当前串的f[len1](假设当前总串长度为len1)那么答案即为了len1-f[len1]，如果f[len1]>=len ,那么答案为len
但是wrong了，，不知道原因
第二次就直接匹配原串和逆串然后就AC了
我把错误代码和正确代码都贴出来，有时间再思考为什么第一个方法错吧，有哪位朋友看到也可以指导，谢啦
错误代码：
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#define maxn 1000005
using namespace std;
char s[maxn];
char s1[maxn*];
int len;
int len1;
int f[maxn*];
void callfail()
{
int i,j=,k=-;
f[]=-;
while(j<len1)
{
if(k==- || s1[j]==s1[k])
{
k++;j++;
f[j]=k;
}
else k=f[k];
}
}
int main()
{
int t;
while(scanf("%d",&t)!=EOF)
{
int iCase=;
while(t--)
{
printf("Case %d: ",iCase++);
s[]='\0';
s1[]='\0';
scanf("%s",s);
len=strlen(s);
for(int i=;i<len;i++)
s1[i]=s[len--i];
s1[len]='\0';
strcat(s1,s);
len1=strlen(s1);
s1[len1]='\0';
callfail();
if(f[len1]>=len)
cout<<len<<endl;
else
cout<<len1-f[len1]<<endl;
}
}
return ;
}
正确代码：
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = ;
char a[maxn];
char b[maxn];
int f[maxn]; void callfail()
{
int len= strlen(b);
f[] =-;
int j=,k=-;
while(j<len)
{
if(k==- || b[k]==b[j])
{
k++;j++;
f[j]=k;
}
else k=f[k];
}
}
int kmp()
{
int la = strlen(a);
int lb = strlen(b);
callfail();
int i=,j = ;
while(i<la && j<lb)
{
if(j==- || a[i]==b[j])
{
i++;j++;
}
else j=f[j];
}
return la + lb - j;
} int main()
{
int t;
scanf("%d", &t);
for (int i = ; i <= t; i++)
{
scanf("%s", a);
int l = strlen(a);
for (int j = ; j < l; j++)
{
b[l-j-] = a[j];
}
b[l] = '\0';
printf("Case %d: %d\n", i, kmp());
}
return ;
}