直接“马拉车”算法
#include <bits/stdc++.h>
#include <string.h>
#include <map>
#include <stack>
using namespace std;
const int maxn=1e7+10;
char temp[maxn<<1];
int P,po,q[maxn<<1];
string str;
int res=1;
int init(string s){ //返回转换后的字符串的长度
int len=s.length();
temp[0]='@';
for(int i=1;i<len*2+1;i+=2){
temp[i]='#';
temp[i+1]=s[i/2];
}
temp[len*2+1]='#';
temp[len*2+2]='$';
return len*2+1;
}
int main(){
int cnt=1;
while(getline(cin,str) && str!="END"){
memset(temp,0,maxn<<1);
memset(q,0,maxn<<1);
res=1,P=0,po=0;
int len=init(str);
for(int i=1;i<=len;i++){
if(P>i) q[i]=min(P-i,q[po*2-i]);
else q[i]=1;
while(temp[i-q[i]]==temp[i+q[i]]){
q[i]++;
}
if(q[i]+i>P) {
P=q[i]+i;
po=i;
}
res=max(q[i],res);
}
cout<<"Case "<<cnt<<": "<<res-1<<endl;
cnt++;
}
system("pause");
return 0;
}