HDU 3068 最长回文 【最长回文子串】

时间：2021-06-12 21:21:49

和上一题一样，不过这题只是要求最长回文子串的长度

在此采用了非常好用的Manacher算法

据说还是O(n) 的效率QAQ

详细用法参考了上篇博客的参考资料，这两天有空学习一下~

Source code:

//#pragma comment(linker, "/STACK:16777216") //for c++ Compiler

#include <stdio.h>

#include <iostream>

#include <fstream>

#include <cstring>

#include <cmath>

#include <stack>

#include <string>

#include <map>

#include <set>

#include <list>

#include <queue>

#include <vector>

#include <algorithm>

#define Max(a,b) (((a) > (b)) ? (a) : (b))

#define Min(a,b) (((a) < (b)) ? (a) : (b))

#define Abs(x) (((x) > 0) ? (x) : (-(x)))

#define MOD 1000000007

#define pi acos(-1.0)

using namespace std;

typedef long long           ll      ;

typedef unsigned long long  ull     ;

typedef unsigned int        uint    ;

typedef unsigned char       uchar   ;

template<class T> inline void checkmin(T &a,T b){if(a>b) a=b;}

template<class T> inline void checkmax(T &a,T b){if(a<b) a=b;}

const double eps = 1e-      ;

const int N =               ;

const int M = *      ;

const ll P = 10000000097ll   ;

char str[M];//start from index 1

int p[M];

char s[M];

int n;

void kp(){

    int i;

    int mx = ;

    int id;

    for(i = ; i < n; ++i){

        if( mx > i )

            p[i] = Min( p[*id-i], p[id]+id-i );

        else

            p[i] = ;

        for(; str[i+p[i]] == str[i-p[i]]; p[i]++)

            ;

        if( p[i] + i > mx ){

            mx = p[i] + i;

            id = i;

        }

    }

}

void pre(){

    int i,j,k;

    n = strlen(s);

    str[] = '$';

    str[] = '#';

    for(i = ; i < n; ++i){

        str[i* + ] = s[i];

        str[i* + ] = '#';

    }

    n = n* + ;

    str[n] = ;

}

int main(){

    int T,_=, t, i, ans;

    while(EOF != scanf("%s", s)){

        ans = ;

        pre();

        kp();

        for(i = ; i < n; ++i)

            checkmax(ans, p[i]);

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

    }

    return ;

}

相关文章