【3068 HDU】最长回文串（Manacher算法）

忘是亡心i 2022-05-10 13:26 241阅读 0赞

题目：[点击打开题目链接][Link 1]

思路：这题要用到回文串匹配的知识点。我们之前遇到这种题传统思想就是分奇数和偶数情况进行暴力，从前往后遍历每一个字符，然后以该字符为中心向两边查找，但这样的时间复杂度很高，是O(n^2/2)，提交的话，肯定会wa。这里介绍一种新的算法，Manacher算法。

Manacher算法的时间复杂度是O(n)，它主要应用于求一个字符串中的最长回文子串的问题。

首先Manacher算法有一个好处就是不用分奇数和偶数的情况。具体操作就是在每个字符之间都加一个\#，将其构成一个新的偶数字符串，例如偶数字符串aaabbc，填充成一个新的字符串后变成“@\#a\#a\#a\#b\#b\#c\#”；奇数字符串aabbc，填充完后形成的字符串就是“@\#a\#a\#b\#b\#c\#”，（这里的@为了防止越界）也就是说不管之前的字符串个数是奇数还是偶数，填充完之后字符串个数都是偶数个。

然后就是Manacher算法有一个核心就是求p\[i\]，p\[i\]的含义就是以第i个字符为中心的最长回文串半径，将字符串中每个字符的p\[i\]都算出来，然后就可以得到这个字符串的最长回文子串长度就是其中最大的p\[i\]-1.例如：（假设初始字符串为ababc）

![70][]

因此，字符串“ababc”的最长回文子串的长度是4-1=3.

那么，问题来了，怎么求 p\[i\] 咧 \\

如果 i 在以pos为中心的回文串中（即i < r，r是以pos为中心的回文串的最右区间），则在回文串中必有一个 j 和 i 与之对称，那么此时p\[i\] = p\[j\]；但是还有一种可能就是我们不知道r以外的字符是否也有相等的，如果有的话，p\[i\]就不是单纯的= p\[j\]了，p\[i\]就是p\[j\] + 半径以外相等的部分，所以求p\[i\]就有了下面2种情况。

![70 1][]![70 2][]

综合上述两种情况，可得p\[i\]的计算方法

if(i < r) 
        p[i] = min(p[2*pos-i],r-i);///取其中小的一个，以确保p[i]是正确的，然后再对r以外的字符进行比较
    else 
        p[i] = 1;
    while(s[i+p[i]] == s[i-p[i]] && i-p[i] >= 0 && i+p[i] < l)///判断半径外的字符还有没有相等的，如果有，就更新回文串的半径长
        p[i]++;

下面，举个栗子

![70 3][]

此时p\[j\] = 4，r-i = 2，然后p\[i\] = r-i = 2.（因为半径以外的字符没有相等的了）

![70 4][]

此时p\[j\] = 2，r-i = 2，但是p\[i\] = 2+2 = 4.（此时半径外还有2个字符相等，因此p\[i\]是4）

然后到这Manacher算法可以算是over咧，还有一点儿是如果 i+p\[i\] > r 的话，需要更新r的值。

下面可以结合代码走一遍。

My DaiMa：

#include<iostream>
    #include<stdio.h>
    #include<string.h>
    #include<algorithm>
    using namespace std;
    char s[220010],a[110005];///s是填充后的字符串
    int len,pos,p[220010],ans,r;///p[i]是以i为中心的最长回文串半径，r是以pos为中心最长回文串半径的最右区间
    void addchar()///在每个字符之间填一个#，构成新的字符串
    {
        s[0] = '@';
        int i = 1, j = 0;
        while(i < 2*len+1)
        {
            s[i++] = '#';
            s[i++] = a[j++];
        }
        s[i++] = '#';
        len = 2*len + 2;
    }
    int Manacher()
    {
        ans = r = pos = 0;///刚开始的pos和r都在第一个字符的地方
        for(int i = 0; i < len; i++)
        {
            if(i < r) p[i] = min(p[2*pos-i],r-i);///取其中小的一个，以确保p[i]是正确的，然后再对r以外的字符进行比较
            else p[i] = 1;
            while(s[i+p[i]] == s[i-p[i]] && i-p[i] >= 0 && i+p[i] < l)///判断半径外的字符还有没有相等的，如果有，就更新回文串的半径长
                p[i]++;
            if(i+p[i] > r)///比较当前的回文串长度有没有超过最右区间，若超过了，则更新最右区间r的值，同时中心点pos也要随之改变
            {
                r = i+p[i];
                pos = i;
            }
            ans = max(ans,p[i]-1);///取其中最长的回文串长度
        }
        return ans;
    }
    int main()
    {
        while(~scanf("%s",a))
        {
            len = strlen(a);
            addchar();
            ans = Manacher();
            cout << ans << endl;
        }
    }

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=3068
[70]: /images/20220505/2c4706c3f5e646a5aff4c83b2221124b.png
[70 1]: https://img-blog.csdn.net/20181018170544402?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTgxNzcy/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 2]: /images/20220505/094b29b117f645fbbc26f2aa3f79e8b5.png
[70 3]: /images/20220505/ad456fbfa1ba4b239f51ceafc7761ac6.png
[70 4]: /images/20220505/4d82df119dfa440d8dab4ce200e2239c.png