大家好,又见面了,我是全栈君。
回文就是正反读都是一样的字符串,如aba, abba等
两组case之间由空行隔开(该空行不用处理)
字符串长度len <= 110000
aaaa abab
4 3
思路:这里讲得非常具体了http://blog.csdn.net/ggggiqnypgjg/article/details/6645824
#include <cstdio> using namespace std; char s[110005],str[220010]; int p[220010]; int main() { int len,i,maxlen,maxindex,ans; while(~scanf("%s",s)) { str[0]='$'; str[1]='#'; for(i=0;s[i];i++) { str[i*2+2]=s[i]; str[i*2+3]='#'; } len=i*2+2; str[len]='#include <cstdio> using namespace std; char s[110005],str[220010]; int p[220010]; int main() { int len,i,maxlen,maxindex,ans; while(~scanf("%s",s)) { str[0]='$'; str[1]='#'; for(i=0;s[i];i++) { str[i*2+2]=s[i]; str[i*2+3]='#'; } len=i*2+2; str[len]='\0'; maxlen=0; for(i=1;i<len;i++) { if(maxlen>i) p[i]=p[2*maxindex-i]<maxlen-i?p[2*maxindex-i]:maxlen-i; else p[i]=1; while(str[i-p[i]]==str[i+p[i]]) { p[i]++; } if(p[i]+i>maxlen) { maxlen=p[i]+i; maxindex=i; } } ans=0; for(i=1;i<len;i++) if(ans<p[i]) ans=p[i]; printf("%d\n",ans-1); } }'; maxlen=0; for(i=1;i<len;i++) { if(maxlen>i) p[i]=p[2*maxindex-i]<maxlen-i?p[2*maxindex-i]:maxlen-i; else p[i]=1; while(str[i-p[i]]==str[i+p[i]]) { p[i]++; } if(p[i]+i>maxlen) { maxlen=p[i]+i; maxindex=i; } } ans=0; for(i=1;i<len;i++) if(ans<p[i]) ans=p[i]; printf("%d\n",ans-1); } }
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/116281.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...