首页 > 代码库 > 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 }
View Code

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 }
View Code

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 }
View Code

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 }
View Code

 

manachar算法小结