M_sea

「总结」Manacher算法
概念$\texttt{Manacher}$是一种$O(n)$求回文串的算法。算法$O(n^3)$枚举左右界$l$、...
扫描右侧二维码阅读全文
24
2019/01

「总结」Manacher算法

概念

$\texttt{Manacher}$是一种$O(n)$求回文串的算法。

算法

$O(n^3)$

枚举左右界$l$、$r$,然后$O(n)\texttt{check}$一遍,这样子是$O(n^3)$的。

$O(n^2)$

枚举对称轴,然后$O(n)$同时向左右扩展,这样子是$O(n^2)$的。

$O(n)$

以上都是废话,这里才是正文

发现一条性质:如果一个回文串里包含着另一个回文串,那么这个回文串的另一边一定存在另一个与它一模一样的回文串。

然后,在原串的每两个字符中插入一个原串中没有的字符(比如~)。

比如ABCDBC,变成~A~B~C~D~B~C~

然后就可以直接以每个字符为对称轴扩展了。

再设$f[i]$表示第$i$个字符向左右能扩展出的回文长度,$MaxRight$表示已经向右触及到了的长度,$mid$表示$MaxRight$的对称轴位置。

这时分两种情况:

  • 当$i$在$mid$右边、$MaxRight$左边时

设$i$关于$mid$的对称点为$j$,显然有$f[i]\geq f[j]$。
然后有$j=mid-(i-mid)=2*mid-i$,于是可以把$f[i]$先赋值成$f[j]$,再扩展。

  • 当$i$在$MaxRight$右边时

此时无法得知有关$i$的情况,于是把$f[i]$复制成$1$,再扩展。

代码

inline void change(char* s) {
    for (re int i=1;i<=n;++i) tmp[i]=s[i];
    for (re int i=1,j=0;i<=n;++i) s[++j]='`',s[++j]=tmp[i];
    s[0]=s[n+n+1]='`';
}

inline void Manacher(char* s,int* f) {
    int MaxRight=0,mid;
    for (re int i=1;i<=n;++i) {
        f[i]=i<MaxRight?min(f[(mid<<1)-i],MaxRight-i):0;
        while (s[i-f[i]-1]==s[i+f[i]+1]) ++f[i];
        if (i+f[i]>MaxRight) MaxRight=i+f[i],mid=i;
    }
}

例题

习题

国家集训队 最长双回文串

不知道比例题简单到哪去了的题目。

最后修改:2019 年 04 月 05 日 01 : 31 PM

1 条评论

  1. LSlzf

    M_sea厉害!!!

发表评论