hdu3068 manacher模板题

给出一个只由小写英文字符a,b,c...y,z组成的字符串S,求S中最长回文串的长度.
回文就是正反读都是一样的字符串,如aba, abba等

Input输入有多组case,不超过120组,每组输入为一行小写英文字符a,b,c...y,z组成的字符串S
两组case之间由空行隔开(该空行不用处理)
字符串长度len <= 110000Output每一行一个整数x,对应一组case,表示该组case的字符串中所包含的最长回文长度.
Sample Input

aaaa

abab

Sample Output

4

3
题意：找最长回文子串
题解：manacher算法，据说这是一道连后缀数组O（nlogn）也卡的神题。。结果真的是，第一次用manacher写也tle了，估计是写搓了改了好几遍

#include<map>

#include<set>

#include<cmath>

#include<queue>

#include<stack>

#include<vector>

#include<cstdio>

#include<iomanip>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#define pi acos(-1)

#define ll long long

#define mod 10007

#define ls l,m,rt<<1

#define rs m+1,r,rt<<1|1

using namespace std;

const double g=10.0,eps=1e-;

const int N=+,maxn=(<<)-,inf=0x3f3f3f3f;

string str;

int p[N],slen;

void manacher()

{

    int mx=,id;

    for(int i=;i<=slen;i++)

    {

        if(mx>i)p[i]=min(p[*id-i],mx-i);

        else p[i]=;

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

        if(p[i]+i>mx)

        {

            mx=p[i]+i;

            id=i;

        }

    }

}

int main()

{

    ios::sync_with_stdio(false);

    cin.tie();

 //   cout<<setiosflags(ios::fixed)<<setprecision(2);

    string s;

    int cnt=;

    while(cin>>s){

        str="$#";

        for(int i=;i<s.size();i++)

        {

            str+=s[i];

            str+="#";

        }

        slen=str.size();

        memset(p,,sizeof p);

        manacher();

        int ans=-;

        for(int i=;i<str.size();i++)

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

       cout<<ans<<endl;

    }

    return ;

}

巴特西

hdu3068 manacher模板题

最新文章

热门文章