浅谈Manacher

\(Manacher\)是由一个叫做\(Manacher\)的人发明的能在\(O(n)\)时间内找出一个字符串长度最长的回文子串的算法。

由于偶回文串形如\(abba\)这样的不好找对称中心，所以我们在每个字符串之间插入一个'#'，就变成#a#b#b#a#了，这样子就能找到对称中心了。

\(Manacher\)的核心数组\(p_i\)：表示以第\(i\)为为对称中心的回文串半径长度为多少(包含\(i\))

#	a	#	a	#	b	#	a	#	a	#
1	2	3	2	1	6	1	2	3	2	1

上面一行是字符串，下面一行是\(p_i\)数组。

以\(i\)为中心的回文串长度即为\(p_i-1\)，这个减一可以看做是把最旁边的那个'#'减掉了，然后半径就跟实际上回文串的长度一样了。

所以\(manacher\)算法的核心就是在\(O(n)\)的时间复杂度内求出\(p\)数组。

令\(mx\)为之前已经求出过的\(p_i+i-1\)的最大值，\(id\)满足\(p_{id}+id-1\)等于\(mx\)的

那么\(p_i= i\leqslant mx?min(mx-i+1,p[id*2-i]):1\)。

这个意思是如果当前位置在\(mx\)左边，那么当前位置的\(p\)肯定是\(mx-i+1\)与我关于\(id\)对称点的\(p\)的最小值。因为那个点与我关于\(id\)对称，所以在\([i,mx]\)这一段内我可以直接继承他的\(p\)数值，但是当前位置已知的回文串长度不能伸到\(mx\)后面去，所以跟\(mx-i+1\)取\(min\)。

然后在暴力判断能不能继续扩张到\(mx\)后面去，最后更新\(id\)和\(mx\)。

时间复杂度分析：

除了暴力扩张\(mx\)以外都是\(O(1)\)的，\(mx\)最多被扩张字符串长度，所以复杂度是\(O(n)\)的。

模板题：https://www.luogu.org/problemnew/show/P3805

时间复杂度：\(O(n)\)

空间复杂度：\(O(n)\)

代码如下：

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int maxn=2.2e7+5;

int n,ans;

int p[maxn];

char s[maxn];

int main() {

    scanf("%s",s+1);

    n=strlen(s+1);

    for(int i=n;i;i--)

        s[i<<1]=s[i],s[(i<<1)-1]='#';

    s[0]='$',s[n<<1|1]='#';n=n<<1|1;

    int id=0,mx=0;

    for(int i=1;i<=n;i++) {

        p[i]=i<=mx?min(mx-i+1,p[id*2-i]):1;

        while(s[i-p[i]]==s[i+p[i]])p[i]++;

        if(i+p[i]-1>mx)id=i,mx=i+p[i]-1;

        ans=max(ans,p[i]);

    }

    printf("%d\n",ans-1);

    return 0;

}

巴特西

浅谈Manacher

最新文章

热门文章