$manacher$算法

前言

写于\(20200202\)（滑稽

算法

现在有这样一个问题：

求一个字符串子串中回文串的数量

俺们会哈希！复杂度\(O(nlogn)\)

但是显然我们今天要讲更优秀的算法~

考虑一下，\(kmp\)算法是如何做到线性匹配的？它重复利用了之前的匹配信息！

那么我们在求回文串问题的时候可不可以也利用之前的匹配信息

比如一个串\(abacaba\)

首先，我们对已经处理过的位置记录一下最大的回文半径\(p_i\)

再记录一个\(mid,r\)，其实\(r\)表示当前已经处理过的回文串中回文半径的右端点，\(mid\)为\(r\)对应的回文中心的位置！

那么这样有什么用呢？

考虑我们扫到一个新的位置\(i\)，那么求出它的回文半径分为以下几种情况：

\(1.\)它在\(r\)的右边，那么没什么好说的，直接暴力扩展~

\(2.\)它在\(r\)的左边，那么说明它本身包含在一个回文串之中，由于回文串的对称性，在\(mid-(i-mid)\)的位置如果是一个回文串，那么它也应该是一个回文串~

需要注意的是，初始化\(p_i=min(r-i,p[mid-(i-mid)])\)，因为超出原本回文的部分并不保证一定回文,然后再慢慢相右扩展

然而我们会发现这样好像没法统计\(aa\)这种偶数长度的回文串，这种情况只要在每个字符中间加入一个没用的字符就好了：\(a\#a\)

那么为什么这样就是线性的呢？

很显然每个位置只会被扫过一个，每个位置也只会被扩展一次，那就是线性的啦

\(code\)

模板

这个是求一个串中最长回文子串

\(int\)类型要有返回值……不然会\(RE\)(小声bb

#include<bits/stdc++.h>
using namespace std;
namespace red{
#define int long long
    const int N=12000000;
    int n=1;
    char s[N<<1],ch;
    int p[N<<1],mid,r,ans;
    inline void read()//魔改过的快读
    {
        s[0]='~';s[1]='#';//"~"防止越界 
        for(ch=getchar();ch<'a'||ch>'z';ch=getchar());
        while(ch>='a'&&ch<='z'){s[++n]=ch;s[++n]='#';ch=getchar();}
    }
    inline void main()
    {
        read();
        for(int i=1;i<=n;++i)
        {
            if(i<r) p[i]=min(r-i,p[(mid<<1)-i]);
            else p[i]=1;
            while(s[i-p[i]]==s[i+p[i]]) ++p[i];
            if(p[i]+i>r) r=i+p[i],mid=i;//更新最右 
            ans=max(ans,p[i]);
        }
        printf("%lld\n",ans-1);
    }
}
signed main()
{
    red::main();
    return 0;
}