[hdu3068 最长回文]Manacher算法，O(N)求最长回文子串

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3068

题意：求一个字符串的最长回文子串

思路：

枚举子串的两个端点，根据回文串的定义来判断其是否是回文串并更新答案，复杂度O(N³)。
枚举回文串的对称轴i，以及回文半径r，由i和r可确定一个子串，然后暴力判断即可。复杂度O(N²）。
在上一步的基础上，改进判断子串是否是回文串的算法。记f_i(r)=(bool)以i为对称轴半径为r的子串是回文串，f_i(r)的值域为{0, 1}，显然f_i(r)是关于r的单调函数，于是可以二分r，然后用字符串hash在O(1)的时间内判断子串是否是回文串，总复杂度O(NlogN)。
虽然O(NlogN)的复杂度已经非常不错了，但还有线性的算法---Manacher算法。

Manacher算法：维护两个值r和id，r是以前的回文串的最大右边界，id是其对应的下标，如果当前考虑的对称轴i小于等于r，那么从i到r这一段子串是否可以和i左边的子串构成回文串（或者说最长能有多长）其实在之前是已经计算过了的（或者说计算出了一部分），因为将i作关于id的对称点i'=2*id-i，就不难发现i^'周围若干字符和i周围若干字符是对应相同的，这是Manacher算法的核心之处，可以用i^'的最大回文半径来更新i的最大回文半径，利用这个性质就能做到线性的复杂度。

#pragma comment(linker, "/STACK:10240000")

#include <bits/stdc++.h>

using namespace std;

#define X                   first

#define Y                   second

#define pb                  push_back

#define mp                  make_pair

#define all(a)              (a).begin(), (a).end()

#define fillchar(a, x)      memset(a, x, sizeof(a))

typedef long long ll;

typedef pair<int, int> pii;

#ifndef ONLINE_JUDGE

namespace Debug {

void print(){cout<<endl;}template<typename T>

void print(const T t){cout<<t<<endl;}template<typename F,typename...R>

void print(const F f,const R...r){cout<<f<<", ";print(r...);}template<typename T>

void print(T*p, T*q){int d=p<q?:-;while(p!=q){cout<<*p<<", ";p+=d;}cout<<endl;}

}

#endif // ONLINE_JUDGE

template<typename T>bool umax(T&a, const T&b){return b<=a?false:(a=b,true);}

template<typename T>bool umin(T&a, const T&b){return b>=a?false:(a=b,true);}

/* -------------------------------------------------------------------------------- */

const int maxn = 3e5 + ;

/** 求字符串每个位置的最大回文半径，在字符串中找最长回文子串 **/

struct Manacher {

    int p[maxn];/** 回文半径 **/

    char s[maxn];

    void init(char str[]) {

        strcpy(s, str);

        int n = strlen(s);

        s[n *  + ] = ;

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

            s[i] = '#';

            s[i - ] = s[i /  - ];

        }

        s[] = '#';

    }

    /** 求每个点的最大回文半径 **/

    void work() {

        int r = , id = ;

        p[] = ;

        for (int i = ; s[i]; i ++) {

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

            if (p[i] >= r - i + ) {

                r = (id = i) + p[i] - ;

                while ( * i - r -  >=  && s[r + ] == s[ * i - r - ]) {

                    r ++;

                    p[i] ++;

                }

            }

        }

    }

    /** 求最长回文串的长度 **/

    int solve() {

        work();

        int ans = ;

        for (int i = ; s[i]; i ++) {

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

        }

        return ans;

    }

};

Manacher solver;

char s[maxn];

int main() {

#ifndef ONLINE_JUDGE

    freopen("in.txt", "r", stdin);

    //freopen("out.txt", "w", stdout);

#endif // ONLINE_JUDGE

    while (~scanf("%s", s)) {

        solver.init(s);

        printf("%d\n", solver.solve());

    }

    return ;

}

秒客网

[hdu3068 最长回文]Manacher算法，O(N)求最长回文子串

相关文章