最长回文串（manacher算法）
浏览数：30 /
时间：2015年06月08日
1 const int LEN=110005; 2 const int N=LEN*2; 3 int p[N]; 4 char str[LEN], tmp[N]; 5 //p[i]表示以str[i]为中心的回文往右延伸的 最长长度 6 void manacher(char* str, int* p){ 7 int n=strlen(str), i, id, mx; 8 for(p[mx=id=0]=i=1; i<n; i++){ 9 p[i]=mx>i?min(p[2*id-i], mx-i+1):1; 10 while(i+p[i]<n&&i-p[i]>=0&&str[i+p[i]]==str[i-p[i]]) p[i]++; 11 if(mx<i+p[i]-1){ 12 id=i; 13 mx=i+p[i]-1; 14 } 15 } 16 } 17 //求str的最长回文的长度 18 int maxPalindrome(char* str){ 19 int ans=0; 20 int i, n; 21 for(i=0, n=strlen(str); i<n; i++){ 22 tmp[2*i]=‘#‘; 23 tmp[2*i+1]=str[i]; 24 } 25 tmp[2*i]=‘#‘; 26 tmp[2*i+1]=‘\0‘; 27 n=n*2+1; 28 manacher(tmp, p); 29 for(i=0; i<n; i++){ 30 if(ans < p[i]-1){ 31 ans = p[i]-1; 32 } 33 } 34 return ans; 35 }
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
