首页 > 代码库 > manacher马拉车算法

manacher马拉车算法

2024-11-18 16:37:39   202人阅读

入门manacher最好文章：https://segmentfault.com/a/1190000003914228

我整理了模板代码：HDOJ3068马拉车模板

技术分享 
 1 //讲解  https://segmentfault.com/a/1190000003914228
 2 //manacher 算法模板
 3 //求最长回文串 O(N)
 4 #include <bits/stdc++.h>
 5 using namespace std;
 6 const int maxn=3e5+10;
 7 char s[maxn],c[maxn];
 8 int RL[maxn],maxright,pos,len;
 9 void init()     //初始化串
10 {
11     len=strlen(c);
12     for(int i=0;i<len;i++)
13     {
14         s[2*i]=‘@‘;
15         s[2*i+1]=c[i];
16     }
17     s[2*len]=‘@‘;
18     s[2*len+1]=‘\0‘;
19     len=2*len+1;
20     maxright=pos=0;
21     //memset(RL,0,sizeof(RL));
22 }
23 
24 int manacher()
25 {
26     RL[0]=1;
27     int ans=1;
28     for(int i=1;i<len;i++)  //枚举对称轴
29     {
30         if(i<=maxright)     //第一种情况处理
31         {
32             int j=2*pos-i;
33             if(j<0)break;
34             RL[i]=min(RL[j],maxright-i);    //跳过重复的步骤
35         }
36         else RL[i]=1;
37         while(s[i-RL[i]]==s[i+RL[i]]&&i-RL[i]>=0&&i+RL[i]<len) RL[i]++;   //探查 新的回文串
38         if(i+RL[i]>=maxright) maxright=i+RL[i],pos=i;  //更新 最右端 和对称轴
39         ans=max(ans,RL[i]);
40     }
41     cout<<endl;
42     return ans-1;
43 }
44 
45 int main()
46 {
47     while(scanf("%s",c)!=EOF)
48     {
49         init();
50         cout<<manacher()<<endl;      //小细节
51     }
52     return 0;
53 }
View Code

 

 

manacher算法能够O(N)求字符串的最长回文字串

回文串就是  ：一个字符串  正读和反着读  是一样的。

举个例子：  12321   abccba   tattarrattat   aaaa  都是回文串

 

先介绍  

1：朴素求法

1：枚举区间左端点和右端点  for(i=0~n) for(j=i~n)　　枚举O(N^2)

2:朴素判断该串是否为回文串　　　　　　　　　　　　判断O(N)

总时间复杂度  O(N^3)  显然 很朴素，很慢

判断字符串是否为回文串：

因为回文串具有中心对称性，所以回文串关于中心对称，可以从对称轴开始向左右移动匹配

 

2：稍加优化

枚举对称轴，从对称轴向两边延伸判断回文串。

由于回文串的长度为奇数和偶数时 对称轴的位置不同，对称轴的位置在字符的位置或是字符之间

对于长度为n的字符串，对称轴共有2*n-1个，每个对称轴平均向旁边延伸n/4个，总时间复杂度是O(N^2).

3:运用动态规划的思想O(N^2)

使用d[i][j]记录区间i到j的字符串是否为回文串

通过状态转移O(1)判断区间内字符串是否为回文串

枚举范围O(N^2);总时间复杂度O(N^2).

 

技术分享 
 1 bool d[maxn][maxn];
 2 char s[maxn];
 3 
 4 void pd()
 5 {
 6     memset(d,0,sizeof(d));          //d[i][j] 表示 区间i~j上的是不是回文串
 7     int maxlen=0;
 8     int len=strlen(s);
 9     int l,r;
10     for(int line=1;line<len;line++)
11     {
12         for(int i=0;i+line-1<len;i++)
13         {
14             int j=i+line-1;
15             if(s[i]==s[j]&&(d[i+1][j-1]||j-i<=2))   //状态转移
16             {
17                 d[i][j]=1;
18                 l=i;
19                 r=j;
20                 maxlen=line;
21 
22             }
23         }
24     }
25 }
View Code

 

 

 

4:manacher (马拉车算法)O(N)

马拉车算法主要解决了两个点

1)这样一种情况：

长回文串中包含的子回文串

ababa   计算了两次aba aba

如果长回文串很长，这种重复计算不可忽视

2)枚举对称轴时，回文串长度奇偶性的影响

通过在串中添加相同字符解决

这样把每个有效字符的下标都设为了奇数，穿插的’#’不会影响回文串

char:    # a # b # a #

  i :     0 1 2 3 4 5 6

 

为了解决重复枚举回文字串的问题，引入一个数组(manacher的核心在这)

RL[i]表示以i为对称轴，向右到i+RL[i]-1向左到i-RL[i]+1 范围的串是回文串。

同时引入maxright记录此时处理过的回文串中最右面的位置

Pos记录该回文串的对称轴。

 

可以看出要处理的对称轴i一定在pos后面

分两种情况：

1)i<=maxright

2)i>maxright

If(i>maxright)  此时要从i开始向左右两侧朴素的查找最长回文串，同时更新maxright和pos

If(i<=maxright)去重就看它。此时对称轴i在一个以pos为对称轴，右边界maxright的回文串之内

i关于pos对称的位置j=2 * pos - i ,

以j为对称轴，范围在pos回文串之内的回文串一定和以i为对称轴的回文串部分相同

例如 b  abababa  c   pos指向中间的b maxright指向最后的a  i在最后的b   j在第二个b

If(RL[j]过大)       i+RL[j]>maxright  RL[i]=maxright-i;

if(RL[j]比较小      If(i+RL[i]<maxright  RL[i]=RL[j]

完成这一步之后i回文串继续向后匹配，同时更新maxright和pos

 

manacher马拉车算法


联系
我们