首页 > 代码库 > manachar算法小结
manachar算法小结
1.hdu--4513 吉哥系列故事——完美队形II
http://acm.hdu.edu.cn/showproblem.php?pid=4513
题意：中文题不解释
思路：数字型的manachar算法。将模板中的比较字符改为比较数字就行了。
AC代码：
1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include <algorithm> 5 #include <cmath> 6 using namespace std; 7 int a[200005],p[200005],k[200005]; 8 int manachar(int len) 9 { 10 int maxn,mx,id,i; 11 maxn=mx=id=0; 12 memset(p,0,sizeof(p)); 13 for(i=1; i<len; i++) 14 { 15 if(mx>i) 16 p[i]=min(p[id*2-i],mx-i); 17 else 18 p[i]=1; 19 for(; a[i-p[i]]==a[i+p[i]]&&p[i]<=k[i]; p[i]++) 20 if(p[i]+i>mx) 21 { 22 mx=p[i]+i; 23 id=i; 24 } 25 if(p[i]>maxn) 26 maxn=p[i]; 27 } 28 printf("%d\n",maxn-1); 29 return 0; 30 } 31 int main() 32 { 33 int i,t,n; 34 while(~scanf("%d",&t)) 35 { 36 while(t--) 37 { 38 scanf("%d",&n); 39 memset(a,0,sizeof(a)); 40 memset(k,0,sizeof(k)); 41 a[0]=-1; 42 for(i=0; i<n; i++) 43 { 44 scanf("%d",&a[i*2+2]); 45 if(a[i*2+2]>=a[i*2]) 46 { 47 k[i*2+1]=k[i*2]+1; 48 k[i*2+2]=k[i*2]+2; 49 } 50 else 51 k[i*2+2]++; 52 //printf("%d %d\n",i*2+2,k[i*2+2]); 53 } 54 manachar(2*n+2); 55 } 56 } 57 return 0; 58 }
2.hdu--3294 Girls‘ research
http://acm.hdu.edu.cn/showproblem.php?pid=3294
题意：先输入一个字符ch表示该字符的real是‘a’，循环对应的ch-1的real是‘z’，再输入一个字符串，求这个字符串real值的最大回文串，如果有多个结果输出第一个。输出最大回文串的左端点值和右端点值，如果回文串长度是1的话打印“No solution!”
思路：先把给的字符串改成real串，再求最大回文串，并记录real串的左右端点。
AC代码：
1 #include <iostream> 2 #include<cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <cmath> 6 using namespace std; 7 char ch,s[200005],str[400005]; 8 int p[400005]; 9 int manachar(int len) 10 { 11 int maxn,mx,id,pi; 12 maxn=mx=id=0; 13 memset(p,0,sizeof(p)); 14 for(int i=1;i<len;i++) 15 { 16 if(mx>i) 17 p[i]=min(p[id*2-i],mx-i); 18 else 19 p[i]=1; 20 for(;str[i-p[i]]==str[i+p[i]];p[i]++) 21 { 22 if(p[i]+i>mx) 23 { 24 mx=p[i]+i; 25 id=i; 26 } 27 } 28 if(maxn<p[i]) 29 { 30 pi=i; 31 maxn=p[i]; 32 } 33 } 34 maxn--; 35 if(maxn<3) 36 printf("No solution!\n"); 37 else 38 { 39 printf("%d %d\n",(pi-maxn)/2,(pi+maxn-2)/2); 40 for(int i=pi-maxn+1;i<=pi+maxn-1;i=i+2) 41 printf("%c",str[i]); 42 printf("\n"); 43 } 44 return 0; 45 } 46 int main() 47 { 48 while(~scanf("%c",&ch)) 49 { 50 getchar(); 51 gets(s); 52 str[0]=‘$‘,str[1]=‘#‘; 53 int len=strlen(s); 54 for(int i=0;i<len;i++) 55 { 56 if(s[i]>=ch) 57 str[i*2+2]=s[i]-(ch-‘a‘); 58 else 59 str[i*2+2]=s[i]+26-(ch-‘a‘); 60 str[i*2+3]=‘#‘; 61 } 62 str[len*2+2]=‘\0‘; 63 manachar(len*2+2); 64 } 65 return 0; 66 }
3.hdu--3613 Best Reward
http://acm.hdu.edu.cn/showproblem.php?pid=3613
题意：先输入‘a’~‘z’的价值，然后给出一个字符串，问把这个字符串分成两部分，如果这一部分是回文串则把总价值加上这部分串的价值，求最大的总价值
思路：先把给出的串的总价值进行累加放入数组中，然后对模式串给出的查询串用manachar算法进行计算，如果当前查询到的i<len/2并且p[i]==i时，就max（ans，num[i-1]）,如果i>len/2并且p[i]==len-i时，就max（ans，num[n]-num[n-p[i]+1]）,如果ans<num[n]在统筹算一下
AC代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <cmath> 6 using namespace std; 7 const int maxn=500005; 8 char s[maxn],str[maxn<<1]; 9 int num[maxn],k[maxn<<1],p[maxn<<1]; 10 int manachar(int len,int n) 11 { 12 int ans,id,mx; 13 id=ans=mx=0; 14 memset(p,0,sizeof(p)); 15 memset(k,0,sizeof(k)); 16 for(int i=1; i<len; i++) 17 { 18 if(mx>i) 19 p[i]=min(p[id*2-i],mx-i); 20 else 21 p[i]=1; 22 for(; str[i-p[i]]==str[i+p[i]]; p[i]++) 23 if(p[i]+i>mx) 24 { 25 mx=p[i]+i; 26 id=i; 27 } 28 if(i<len/2&&p[i]==i) 29 { 30 ans=max(ans,num[i-1]); 31 k[i]=i*2-1; 32 } 33 else if(i>len/2&&p[i]==len-i) 34 { 35 ans=max(ans,num[n]-num[n-p[i]+1]); 36 k[i]=i*2-len+1; 37 } 38 } 39 for(int i=1; i<len/2; i++) 40 if(k[i]==k[len/2+i-1]&&k[i]!=0) 41 { 42 ans=max(ans,num[n]); 43 break; 44 } 45 printf("%d\n",ans); 46 return 0; 47 } 48 int main() 49 { 50 int a[26],t; 51 while(~scanf("%d",&t)) 52 { 53 while(t--) 54 { 55 for(int i=0; i<26; i++) 56 scanf("%d",&a[i]); 57 scanf("%s",s); 58 int len=strlen(s); 59 memset(str,‘#‘,sizeof(str)); 60 memset(num,0,sizeof(num)); 61 str[0]=‘$‘; 62 for(int i=0; i<len; i++) 63 { 64 str[i*2+2]=s[i]; 65 num[i+1]=num[i]+a[s[i]-‘a‘]; 66 } 67 manachar(len*2+2,len); 68 } 69 } 70 return 0; 71 }
4.poj--3974 Palindrome
http://poj.org/problem?id=3974
题意：给出一系列字符串以“END”结束，问每个字符串的最大回文串的长度
思路：manachar算法直接算。
AC代码：
1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include <algorithm> 5 #include <cmath> 6 using namespace std; 7 int p[2000005]; 8 char s[1000005],str[2000005]; 9 int manachar(int len) 10 { 11 int maxn,mx,id,i; 12 maxn=mx=id=0; 13 memset(p,0,sizeof(p)); 14 for(i=1; i<len; i++) 15 { 16 if(mx>i) 17 p[i]=min(p[id*2-i],mx-i); 18 else 19 p[i]=1; 20 for(; str[i-p[i]]==str[i+p[i]]; p[i]++) 21 if(p[i]+i>mx) 22 { 23 mx=p[i]+i; 24 id=i; 25 } 26 maxn=max(maxn,p[i]); 27 } 28 printf("%d\n",maxn-1); 29 return 0; 30 } 31 int main() 32 { 33 int t; 34 t=1; 35 while(~scanf("%s",s)) 36 { 37 if(strcmp(s,"END")==0) 38 break; 39 int len=strlen(s); 40 memset(str,‘#‘,sizeof(str)); 41 str[0]=‘$‘; 42 for(int i=0; i<len; i++) 43 { 44 str[i*2+2]=s[i]; 45 } 46 str[len*2+2]=‘\0‘; 47 printf("Case %d: ",t++); 48 manachar(len*2+2); 49 } 50 return 0; 51 }
manachar算法小结
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。