【模板——ing】O(n)回文子串（Manacher）算法

系统管理员 2022-06-07 02:55 161阅读 0赞

1.模板适应问题：  
（1）：输入串st，求出串st中最长回文子串

2.模板代码：

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace  std;
    
    const int size_len1 = 110414;
    const int size_len2 = size_len1<<1;
    
    char str1[size_len1], str2[size_len2];
    int pt[size_len2];
    
    void Manacher(char *st1, char *st2);
    
    int main(){
        while(~scanf("%s", str1)){
            Manacher(str1, str2);
        }
        return 0;
    }
    void Manacher(char *st1, char *st2){
        int k = 1, i;
        int len1 = strlen(st1);
        st2[0] = '$';
        for(i = 0; i < len1; i++){
            st2[k++] = '#';
            st2[k++] = st1[i];
        }
        st2[k++] = '#';
        st2[k] = '\0';
    
        int mx = 0, id = 0, mav = 0, v;
        memset(pt, 0, sizeof(pt));
        for(i = 1; i < k; i++){
            if(mx > i)
                pt[i] = min(pt[(id<<1)-i], mx-i);
            else
                pt[i] = 1;
            while(st2[i-pt[i]] == st2[i+pt[i]]){
                pt[i]++;
            }
            if(i+pt[i] > mx){
                id = i;
                mx = i + pt[i];
            }
            if(mav < pt[i]){
                v = i;
                mav = pt[i];
            }
        }
    
        mav -= 1;
    
        /*输出最长回文串长度*/
        printf("%d\n", mav);
    
        /*输出最长回文串,长度相等则输出最先出现的最长回文串*/
        int star = v - mav;
        int endd = v + mav;
        for(i = star; i <= endd; i++){
            if(st2[i] != '#')
                printf("%c", st2[i]);
        }
        printf("\n");
    
    }

3.算法学习：  
[建议参考博客——算法分析][Link 1]

4.题目练习：  
[最长回文 HDU - 3068——vjudge题目链接][HDU - 3068_vjudge]

[Link 1]: http://www.cnblogs.com/biyeymyhjob/archive/2012/10/04/2711527.html
[HDU - 3068_vjudge]: https://vjudge.net/problem/HDU-3068