马拉车（manacher） 算法

前言

马拉车算法（Manacher's algorithm）是一个求一个字符串中最长回文连续子序列的算法

其实是自己复习用的（

正文

【模板】manacher算法

题意是求S中的最长回文串

最暴力的做法当然是枚举l和r，对于每个l和r求遍历一遍判断是否为回文

时间复杂度达到O(n^3)，显然做不了这题

在这个基础上稍微优化一下，也是很显然的做法：长度为奇数回文串以最中间字符的位置为对称轴左右对称，而长度为偶数的回文串的对称轴在中间两个字符之间的空隙。可以遍历这些对称轴，在每个对称轴上同时向左和向右扩展，直到左右两边的字符不同或者到达边界。

这样的复杂度是O(n^2)，还是过不了

观察数据范围，S.length()\leq11000000，应该需要一个O(n)及以下的算法

dalao云

暴力算法的优化是信息的利用和对重复搜索的去重

我们考虑如何利用这里的重复信息

第一种解法，是直接暴力计算

而第二种解法，是利用字符串对称的性质，把枚举端点变成枚举中点，少了一个循环，优化掉O(n)的复杂度

我们所求的O(n)算法，是不是能由第二种解法再利用一次字符串对称的性质得来呢？

观察下面的字符串:

O A K A B A K A B A O A K

其中的最长回文串为ABAKABA，若使用第二种解法，有什么可以不计算的呢？

相信很容易猜到，一个回文串的左半边有一个回文串，那它的右半边也有一个，那么我们对这个回文串的计算显然可以略去

扩展到一般性质，若一个回文串里包含着另一个回文串，那这个回文串的另一边必然存在另一个与它一模一样的回文串!

由此我们来改进第二种算法

这个O(n^2)算法有什么缺点呢?

1. 回文串长度的奇偶性造成了对称轴的位置可能在某字符上，也可能在两个字符之间的空隙处，要对两种情况分别处理

如何解决？我们可以强行在原字符串中插入其他本字符串不会出现的字符，如"#"

也就是说，若原来的字符串是这样

那么我们把它改成这样

关于这部分的代码：

inline void change() {
    s[0]=s[1]='#';
    for(int i=0; i<n; i++) {
        s[i*2+2]=a[i];
        s[i*2+3]='#';
    }
    n=n*2+2;
    s[n]=0;
}

这样我们就可以直接以每个字符为对称轴进行扩展了

2. 会出现很多子串被重复多次访问，时间效率大幅降低。

这个就是我们刚刚提出的优化了。

我们用一个辅助数组hw_i表示i点能够扩展出的回文长度

我们先设置一个辅助变量maxright，表示已经触及到的最右边的字符

以及一个辅助变量mid，表示包含maxright的回文串的对称轴所在的位置

也就是这样：

当i在maxright左边且在mid右边时：

设i关于mid的对称点为j，显然hw_i一定不会小于hw_j。

我们没必要保存j，j可以通过计算得出，为mid+(mid-i)=(mid\times2)-i

那么我们就将hw_i设为hw_j，从i+hw_i开始扩展（利用已知信息），这样就可以较快地求出hw[i]，然后重新maxright和mid

当i在maxright右边时，我们无法得知关于hw_i的信息，只好从1开始遍历，然后更新maxright和mid

这部分的代码也是非常简短的:

inline void manacher() {
    int maxright=0,mid;
    for(int i=1; i<n; i++) {
        if(i<maxright)
            hw[i]=min(hw[(mid<<1)-i],hw[mid]+mid-i);
        else
            hw[i]=1;
        while(s[i+hw[i]]==s[i-hw[i]])
            ++hw[i];
        if(hw[i]+i>maxright) {
            maxright=hw[i]+i;
            mid=i;
        }
    }
}

虽然看起来优化不了多少，但它的时间复杂度确实是O(n)的，下面证明一下

分两种情况讨论

1.在遍历i的时候，maxright没有右移

那么hw_i可以直接得出，计算是O(1)的

2.在遍历i的时候，maxright右移了

这个时候，设maxright右移了s个单位

因为maxright需要右移n个单位，所以复杂度是O(n)

习题

P4555 [国家集训队]最长双回文串

一道几乎是裸题的题

看到回文串可以想想马拉车，于是我们就用马拉车写

在朴素的马拉车基础上求出l和r数组，l_i表示i所在回文串中的最右端的下标，r_i代表i所在回文串中的最左端的下标

然后拼接一下即可：

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

const int maxn=200010;
char a[maxn],s[maxn<<1];
int l[maxn<<1],r[maxn<<1];
int n,hw[maxn],ans;
inline void manacher() {
    int maxright=0,mid;
    for(int i=1; i<n; ++i) {
        if(i<maxright)
            hw[i]=min(hw[(mid<<1)-i],hw[mid]+mid-i);
        else
            hw[i]=1;
        while(s[i+hw[i]]==s[i-hw[i]])
            ++hw[i];
        if(hw[i]+i>maxright) {
            maxright=hw[i]+i;
            mid=i;
        }
    }
}

void change() {
    s[0]=s[1]='#';
    for(int i=0; i<n; ++i) {
        s[i*2+2]=a[i];
        s[i*2+3]='#';
    }
    n=n*2+2;
    s[n]=0;
}

inline int maxx(int a,int b) {
    return a>b?a:b;
}

int main() {
    scanf("%s",a);
    n=strlen(a);
    change();
    manacher();
    int now=0;
    for(int i=0; i<n; ++i)
        while(now<=i+hw[i]-1)
            l[now++]=i;
    now=n;
    for(int i=n-1; i>=0; --i) {
        while(now>=i-hw[i]+1)
            r[now--]=i;
    }
    int ans=0;
    for(int i=0; i<n; ++i)
        ans=maxx(ans,r[i]-l[i]);
    printf("%d",ans);
}

SP7586 NUMOFPAL - Number of Palindromes

求一个串中包含几个回文串

用马拉车求出以每个字母为对称轴的回文串长度，因为一个回文串长度/2就是这个回文串包含的子回文串长度，所以最后统计一下即可~

#include<cstdio>
#include<iostream>
#include<cstring>
#define maxn 51000100
using namespace std;
int n,hw[maxn],ans;
char a[maxn],s[maxn<<1];
void manacher()
{
    int maxright=0,mid;
    for(int i=1;i<n;i++)
    {
        if(i<maxright)
            hw[i]=min(hw[(mid<<1)-i],hw[mid]+mid-i);
        else
            hw[i]=1;
        while(s[i+hw[i]]==s[i-hw[i]])
            ++hw[i];
        if(hw[i]+i>maxright)
        {
            maxright=hw[i]+i;
            mid=i;
        }
    }
}
void change()
{
    s[0]=s[1]='#';
    for(int i=0;i<n;i++)
    {
        s[i*2+2]=a[i];
        s[i*2+3]='#';
    }
    n=n*2+2;
    s[n]=0;
}
int main()
{
    scanf("%s",a);
    n=strlen(a);
    change();
    manacher();
    ans=1;
    for(int i=0;i<n;i++)
        ans+=hw[i]/2;
    printf("%d",ans-1);
    return 0; 
}