本文共 2503 字，大约阅读时间需要 8 分钟。
//// main.cpp// 马拉车//// Created by liuzhe on 16/11/26.// Copyright © 2016年 my_code. All rights reserved.//#include#include #include #include #include using namespace std;const int MAX=200000+10; char s[MAX*2],temp[2]; int p[MAX*2]; int main(){ while(scanf("%s%s",temp,s)!=EOF){ int len=strlen(s),id=0,maxid=0; for(int i=len;i>=0;--i){ s[i+i+2]=s[i]; s[i+i+1]='#'; } s[0]='*'; for(int i=2;i<2*len+1;++i){ if(p[id]+id>i)p[i]=min(p[2*id-i],p[id]+id-i); else p[i]=1; while(s[i+p[i]] == s[i-p[i]])++p[i]; if(id+p[id]
题意：求最长回文子串所在的区间，然后第一个字符代表a,以后的顺推，最后输出这个区间顺推后的串思路：Manacher轻松水过，记录下最长回文串的位置和长度就行了，然后输出时自己处理一下，大水题.......[html] view plain copy#include#include #include #include #include using namespace std; typedef long long ll; const int inf=0x3f3f3f3f; const int maxn=200010; char str[maxn],tmp[maxn<<1]; int len1[maxn<<1],pos; int init(char *st){ int len=strlen(st); tmp[0]='@'; for(int i=1;i<=2*len;i+=2){ tmp[i]='#'; tmp[i+1]=st[i/2]; } tmp[2*len+1]='#'; tmp[2*len+2]='$'; tmp[2*len+3]=0; return 2*len+1; } int Manacher(char *st,int len){ int p=0,ans=0,po=0; for(int i=1;i<=len;i++){ if(p>i) len1[i]=min(p-i,len1[2*po-i]); else len1[i]=1; while(st[i-len1[i]]==st[i+len1[i]]) len1[i]++; if(len1[i]+i>p){ p=len1[i]+i; po=i; } if(len1[i]>ans){ ans=len1[i]; pos=i; } } return ans-1; } int main(){ char ch; while(scanf(" %c%s",&ch,str)!=-1){ init(str); int len=init(str); int ans=Manacher(tmp,len); if(ans==1) printf("No solution!\n"); else{ int le,ri; if(pos%2==0){ le=pos/2-1-ans/2; ri=le+ans-1; }else{ le=pos/2-ans/2; ri=le+ans-1; } printf("%d %d\n",le,ri); int t=ch-'a'; for(int i=le;i<=ri;i++){ int k=str[i]-t; if(k>=97) printf("%c",str[i]-t); else printf("%c",str[i]-t+26); } printf("\n"); } } return 0; }
转载地址：http://hiali.baihongyu.com/