最长回文子串模板 (Manacher算法,时间复杂度O(n)).docx

/最长回文子串模板/hdu3068，最长回文子串模板，Manacher算法，时间复杂度O(n)，相当快#include#include#includeusing namespace std;#define M 20000050char str1M,str2*M;/start from index 1int radM,nn,n;void Manacher(int *rad,char *str,int n)/*str是这样一个字符串（下标从1开始）：举例：若原字符串为abcd，则str为$#a#b#c#d#，最后还有一个终止符。n为str的长度，若原字符串长度为nn，则n=2*nn+2。radi表示回文的半径，即最大的j满足stri-j+1.i = stri+1.i+j，而radi-1即为以stri为中心的回文子串在原串中的长度*/ int i; int mx = 0; int id; for(i=1; i i )radi = rad2*id-i mx ) mx = radi + i; id = i; int main()int i,ans,Case=1;while(scanf(%s,str1)!=EOF)nn=strlen(str1);n=2*nn+2;str0=$;for(i=0;i=nn;i+)str2*i+1=#;str2*i+2=str1i;Manacher(rad,str,n);ans=1;for(i=0;ians?radi:ans;printf(%dn,ans-1);return 0;/扩展kmp版，时间复杂度O(nlogn)，稍慢/hdu3068/*给一个w长的字符串，求最长回文子串的长度解题思路：不是传说中的高深的后缀数组，而是扩展的kmp算法。扩展kmp中，模式串与主串都有一个next向量，相应的nexti,记录该串的后缀与模式串的最大匹配数，关于扩展kmp的具体实现这里就不说了，现在只说一下解此题的思路：令所给字符串为a，则找到中点mid位置，一后半段做为模式串，把a倒过来生成b，求出b串在该模式串的每一位的next1i;在以字符串a的前半段的逆串作为模式串，求出a串在该模式串下的next2。然后遍历a串的每一位，根据next1和next2就可以判断此处是否回文，但这个回文只能判断跨越中点mid的回文，因此这里要进行划分递归，分别在a的前半段和后半段重复此算法即可找到最大回文串。*/#include#include#includeusing namespace std;#define N 110005char tmp1N,tmp2N,sN,ttN;int tmpN,ans,ne1N,ne2N;char *rev(char *str,int ll)for(int i=0;ill;i+)tti=strll-i-1;ttll=0;return tt;void getA(char *pat,int *aa)int j=0;while(pat1+j & patj=pat1+j)j+;aa1=j;int k=1;int len,l;for(int i=2;pati;i+)len=k+aak;l=aai-k;if(llen-i)?0:len-i;while(pati+j & patj=pati+j)j+;aai=j;k=i;void getB(char *pat,char *str,int *bb,int length)getA(pat,tmp);int j=0;while(patj & strj & patj=strj)j+;bb0=j;int k=0;int len,l;for(int i=1;ilength;i+)len=k+bbk;l=tmpi-k;if(llen-i)?0:len-i;while(i+jlength & patj & patj=stri+j)j+;bbi=j;k=i;void find(int l,int r)if(r-l+1=ans)return;int x;int mid=(l+r)/2;strncpy(tmp1,s+l,mid-l+1);tmp1mid-l+1=0;strncpy(tmp2,s+mid+1,r-mid);tmp2r-mid=0;getB(tmp2,rev(s+l,r-l+1),ne1,r-l+1);getB(rev(tmp1,mid-l+1),s+l,ne2,r-l+1);ne1r-l+1=ne2r-l+1=0;for(int i=l;i=mid-i+1)x=mid-i+1+ne1r-i+1*2;if(ansx)ans=x;if(ans2*ne2mid+1-l)ans=2*ne2mid+1-l;for(int i=mid+1;i=i-mid)x=i-mid+ne2i-l+1*2;if(ansx)ans=x;find(l,mid);find(mid+1,r);int main()while(scanf(%s,s)!=EOF)ans=1;find(0,strlen(s)-1);printf(%dn,ans);return 0;/下面注释掉的也对，只要把上面的rev函数换成下面的rev函数，并把find函数换成下面的solve函数就可以了/*int nextbN,nexta1N,nexta2N;char aN,bN;void rev(char *a,int len) char t; for(int i=0;ilen/2;i+) t=ai,ai=alen-1-i,alen-1-i=t;void solve(char *a,int len) if(len=ans|len1; int i,j,k; for(i=mid;ilen;i+) bi-mid=ai; bi-mid=0; rev(a,len); getB(b,a,nexta1,len); rev(a,len); for(i=0;imid;i+) bi=amid-i-1; bi=0; getB(b,a,nexta2,len); nexta1len=nexta2len=0; for(i=0;i=(mid-i)/2) int x=mid-i+2*nexta1len-i; if(xans)ans=x; for(i=mid;i=(i-mid)/2) int x=i-mid+2*nexta2i; if(xans)an