前言
这个马拉车算法Manacher‘s Algorithm是用来查找一个字符串的最长回文子串的线性方法,由一个叫Manacher的人在1975年发明的,这个方法的最大贡献是在于将时间复杂度提升到了线性,这是非常了不起的。
啥是回文串呢?
形如”aaa” “abba”这样正反读都一样的串叫做回文串。
回文串分两种,一种是偶数长度的回文串,关于中心线对称
另一种是奇数长度的回文串,关于中心点对称
Manacher的原理及实现
首先我们需要对串改造一下
串 “aabbaa”
我们在每个字符的前后都加上一个符’#’
变成 “#a#a#b#b#a#a#”
这样不管是奇数长度串或者是偶数长度串都可以变成奇数长度的了。
另外,在实际操作里,为了防止越界RE,我们会在串头和串尾加上两个不同的字符。
对于新串,定义数组P[i]表示以i这个位置为中心的最大回文串半径
按照朴素的算法,可以直接向两边走,这样复杂度为O(n^2)。
在kmp里,我们进行快速匹配时,利用了一个思想。
那就是在匹配过程中利用之前得到的信息进行匹配。
在马拉车里也是如此
定义id为当前最大回文子串中心的位置,right是回文串能延伸到的最右端的位置.
核心代码
p[i]=right>i?min(p[2*id-i],right-i):1;
我们拆开来看
当
最后,当i >=right没有可用信息,只能去朴素匹配了。
模板题目
https://www.luogu.org/problemnew/show/P3805
注意,题目数据范围不太对。
Code 1(string版)
速度较慢,不建议使用
#include <cstdio>
#include <vector>
#include <string>
#include <cstring>
#include <iostream>
using namespace std;
int p[33000000];
int Manacher(string s)
{
string res = "$#";
for(int i=0;i<s.size();i++)
res+=s[i],res+="#";
int id=0,right=0,ans=0;
for(int i=1;i<res.size();i++)
{
p[i]=right>i?min(p[2*id-i],right-i):1;
while(res[p[i]+i]==res[i-p[i]]) p[i]++;
if(p[i]+i>right) id=i,right=p[i]+i;
ans=max(ans,p[i]-1);
}
return ans;
}
int main()
{
//freopen("data.in","r",stdin);
//freopen("right.out","w",stdout);
string s;
cin>>(s);
return printf("%d",Manacher(s))*0;
}
Code 2(char版)
比String快了将近4倍
#include <cstdio>
#include <vector>
#include <string>
#include <cstring>
#include <iostream>
using namespace std;
int p[51000000];
char res[50000000];
char s[51000000];
int Manacher()
{
res[0]='$',res[1]='#';
int len=1;
int sx=strlen(s);
for(int i=0;i<sx;i++)
res[++len]=s[i],res[++len]='#';
res[++len]='\n';
int id=0,right=0;
int ans=0;
for(int i=1;i<len;i++)
{
p[i]=right>i?min(p[2*id-i],right-i):1;
while(res[p[i]+i]==res[i-p[i]]) p[i]++;
if(p[i]+i>right) id=i,right=p[i]+i;
ans=max(ans,p[i]-1);
}
return ans;
}
int main()
{
scanf("%s",s);
return printf("%d",Manacher())*0;
}