Manacher's Algorithm 马拉车算法（求最长回文串）

作用：求一个字符串中的最长子串，同时还可以求所有子串的长度。

题目链接:

https://vjudge.net/contest/254692#problem/B

最长回文串长度的代码：

 1 int  Manacher(string s)
 2 {
 3     string t = "$#";
 4     for (int i = 0; i < s.size(); ++i)
 5     {
 6         t += s[i];
 7         t += "#";
 8     }
 9     vector<int> p(t.size(), 0);
10     int maxx=0;
11     int mx = 0, id = 0, resLen = 0, resCenter = 0;
12     for (int i = 1; i < t.size(); ++i)
13     {
14       //  maxx=max(maxx,p[i]);
15         p[i] = mx > i ? min(p[2 * id - i], mx - i) : 1;
16         while (t[i + p[i]] == t[i - p[i]])
17             ++p[i];
18         if (mx < i + p[i])
19         {
20             mx = i + p[i];
21             id = i;
22         }
23         if (resLen < p[i])
24         {
25             resLen = p[i];
26             resCenter = i;
27         }
28             maxx=max(maxx,p[i]);
29     }
30     return maxx-1;
31 }

代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 # define maxn 20000+10
 4 char str1[maxn];
 5 char str2[maxn*2];
 6 int p[maxn*2];
 7 int l=0;
 8 int ma()
 9 {
10     int id=0,mx=0;
11     int ans=0;
12     str2[l]='';
13     for(int i=0; i<l+2; i++)p[i]=0;
14     for(int i=1; i<l; i++)
15     {
16         if(i<mx)p[i]=min(p[2*id-i],mx-i);
17         else p[i]=1;
18         while(str2[i-p[i]]==str2[i+p[i]])
19             p[i]++;
20         if(mx<i+p[i])
21         {
22             id=i;
23             mx=i+p[i];
24         }
25         ans+=p[i]/2;
26     }
27     return ans;
28 }
29 int main()
30 {
31     int n;
32     scanf("%d",&n);
33     scanf("%s",str1);
34     str2[l++]='$';
35     str2[l++]='#';
36     for(int i=0; i<n; i++)
37     {
38         if(str1[i]=='-')
39         {
40             if(l-2!=0)l-=2;
41         }
42         else
43         {
44             str2[l++]=str1[i];
45             str2[l++]='#';
46         }
47         printf("%d",ma());
48         if(i!=n-1)printf(" ");
49     }
50     printf("
");
51     return 0;
52 }

上面这个版本的manacher在处理多组输入的时候不如下面这个省时间。

 1 void Manacher(int n)
 2 {
 3     int i, id=0, len=1;
 4 
 5     Estr[0] = '$';
 6 
 7     for(i=start[n]; i<start[n+1]; i++)
 8     {
 9         Estr[len++] = '#';
10         Estr[len++] = MumStr[i];
11 
12         suffix[i] = false;
13         prefix[i] = false;
14     }
15     Estr[len] = '#';
16     Estr[len+1] = 0;
17 
18     for(i=2; i<len; i++)
19     {
20         p[i] = 1;
21 
22         if(p[id]+id > i)
23             p[i] = min(p[id*2-i], p[id]+id-i);
24 
25         while(Estr[ i+p[i] ] == Estr[ i-p[i] ])
26             p[i]++;
27 
28         if(p[id]+id < p[i]+i)
29             id = i;
30   }
31 }