【洛谷 P3805】【模板】manacher算法

题目链接

manacher算法：在线性时间内求一个字符串中所有/最长回文串的算法。

先来考虑一下暴力的算法，枚举每个中点，向两边扩展，时间复杂度\(O(n^2)\)。

来分析下此算法的缺点。

1、因为回文串有奇偶之分，所以要分类讨论，\(abba\)的对称轴不在字符上，分类讨论就会有点麻烦。

为此，\(manacher\)算法的解决方案是在每个字符之间插入一个相同的字符，比如说\(\#\)，

\(ababa->\#a\#b\#a\#b\#a\#\)，这样就不用考虑回文串的奇偶性了。

2、效率低。为什么低？每个位置会被重复遍历。和\(KMP\)算法类似，\(manacher\)也是利用已有信息减少重复无用操作。

比如说\(abacaba\)，这是一个回文串，但两边的\(aba\)也都是一个回文串,我们在枚举到右边的\(b\)时就已经能确定已这个\(b\)为中心的回文串的回文半径至少为\(2\)，然后直接从这个长度开始拓展就好了。设\(hw[i]\)表示以\(a[i]\)为回文中心的回文半径长度，\(maxright\)表示当前已发现的右端点最右的右端点，\(mid\)表示这个回文串的中心。

则有如下算法（我觉得看代码比看讲解容易懂些）

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

   if(i < maxright)

     hw[i] = min(hw[(mid << 1) - i], hw[mid] + mid - i);    //min左边的参数是这个点的对称点的hw值，右边的是保证这个部分在这个大回文串之内

   else hw[i] = 1;

   while(a[i + hw[i]] == a[i - hw[i]]) ++hw[i];  //拓展

   if(hw[i] + i > maxright){   //更新右端点

     maxright = hw[i] + i;

     mid = i;

   }

}

该题完整代码

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int MAXN = 11000010;

char b[MAXN], a[MAXN << 1];

int hw[MAXN << 1], ans, n;

int main(){

    scanf("%s", b);

    a[0] = a[1] = '#';

    int len = strlen(b);

    for(int i = 0; i < len; ++i)

       a[(i << 1) + 2] = b[i], a[(i << 1) + 3] = '#';

    int maxright = 0, mid; len = (len << 1) + 3;

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

       if(i < maxright)

         hw[i] = min(hw[(mid << 1) - i], hw[mid] + mid - i);

       else hw[i] = 1;

       while(a[i + hw[i]] == a[i - hw[i]]) ++hw[i];

       if(hw[i] + i > maxright){

         maxright = hw[i] + i;

         mid = i;

       }

       ans = max(ans, hw[i] - 1);

    }

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

    return 0;

}

巴特西

【洛谷 P3805】【模板】manacher算法

最新文章

热门文章

巴特西

【洛谷 P3805】 【模板】manacher算法

最新文章

热门文章

【洛谷 P3805】【模板】manacher算法