Manacher算法求最长回文子串

Manacher

引例：P3805 【模板】manacher算法(https://www.luogu.org/problem/P3805)

题目描述

给出一个只由小写英文字符a,b,c...y,z组成的字符串S,求S中最长回文串的长度.

字符串长度为n

输入格式

一行小写英文字符a,b,c...y,z组成的字符串S

输出格式

一个整数表示答案

输入输出样例

输入 #1

aaa

输出 #1

说明/提示

字符串长度len <= 11000000

前为老板的标程int代码

后为网上巨佬的void代码

 1 #include<stdio.h>
 2 #include<bits/stdc++.h>
 3 using namespace std; 
 4 char st[51000100],s[51000100];
 5 int R[51000100];
 6 int Init()
 7 {
 8     int len = strlen(st);
 9     s[0] = '@';
10     s[1] = '#';
11     int j = 2;
12     for (int i = 0; i < len; i++)
13     {
14         s[j++] = st[i];
15         s[j++] = '#';
16     }
17     s[j] = ''; // 末尾添字符串结束符
18     return j; // 返回修改后的字符串的长度
19 }
20 int Manacher()
21 {
22     int len = Init(); // 在原串中插入特殊符号，并得到新字符串的长度len
23     int Ans= -1; // 最长回文长度
24     int P=0;
25     int MaxLen = 0;
26     for (int i = 1; i < len; i++)
27     {
28         if (i < MaxLen)R[i] = min(R[2 * P - i], MaxLen-i+1);
29         else R[i] = 1;
30         while (s[i - R[i]] == s[i + R[i]])R[i]++; //不用判断边界，在Init()中对边界做了处理
31         if (MaxLen < i + R[i]-1)
32         {
33             P = i;
34             MaxLen = i + R[i]-1;
35         }
36         Ans = max(Ans, R[i] - 1);
37     }
38     return Ans;
39 }
40 
41 int main()
42 {
43     scanf("%s",st);
44     cout<<Manacher();
45 }
46

 1 #include<stdio.h>
 2 #include<bits/stdc++.h>
 3 #define maxn 51000100
 4 using namespace std;
 5 int n,hw[maxn],ans;
 6 char a[maxn],s[maxn];
 7 void manacher()
 8 {
 9     int maxright=0,mid;
10     for(int i=1;i<n;i++)
11     {
12         if(i<maxright)
13             hw[i]=min(hw[(mid<<1)-i],hw[mid]+mid-i);
14         else
15             hw[i]=1;
16         for(;s[i+hw[i]]==s[i-hw[i]];++hw[i]);
17         if(hw[i]+i>maxright)
18         {
19             maxright=hw[i]+i;
20             mid=i;
21         }
22     }
23 }
24 void change()
25 {
26     s[0]=s[1]='#';
27     for(int i=0;i<n;i++)
28     {
29         s[i*2+2]=a[i];
30         s[i*2+3]='#';
31     }
32     n=n*2+2;
33     s[n]=0;
34 }
35 int main()
36 {
37     scanf("%s",a);
38     n=strlen(a);
39     change();
40     manacher();
41     ans=1;
42     for(int i=0;i<n;i++)
43         ans=max(ans,hw[i]);
44    cout<<ans-1;
45     return 0; 
46 }

Manacher算法 求最长回文子串

Manacher

Manacher算法求最长回文子串