字符串匹配之马拉车算法

前言

这个马拉车算法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;

我们拆开来看

right−i>P[j] 时很明显有P[i]==P[j]

当 P[j]>=right−i 的时候，以S[j]为中心的回文子串不一定完全包含于以S[id]为中心的回文子串中，但是基于对称性可知，下图中两个绿框所包围的部分是相同的，也就是说以S[i]为中心的回文子串，其向右至少会扩张到mx的位置，也就是说 P[i] >= right - i。至于right之后的部分是否对称，就只能老老实实去匹配了
最后，当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;
}