美文网首页
hdu 3068 Manacher

hdu 3068 Manacher

作者: Out_Of_Cage | 来源:发表于2017-04-14 10:36 被阅读0次

    hdu 3068
    求一个字符串的最长回文长度。
    套用Manacher模板即可。

    // hdu 3068
    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    #include <math.h>
    #include <time.h>
    #include <iostream>
    #include <algorithm>
    #include <string>
    #include <set>
    #include <map>
    #include <queue>
    #include <stack>
    #include <bitset>
    #include <vector>
    using namespace std;
    
    #define bll long long
    #define dou double
    #define For(i,a,b) for (int i=(a),_##i=(b); i<=_##i; ++i)
    #define Rof(i,a,b) for (int i=(a),_##i=(b); i>=_##i; --i)
    #define Mem(a,b) memset(a,b,sizeof(a))
    #define Cpy(a,b) memcpy(a,b,sizeof(b))
    
    const int maxn=110000*2+100;
    int P[maxn];
    char s[maxn],str[maxn];
    
    void Manacher(char s[],char str[],int P[])
    {
        int n=strlen(s+1);
        int len=n<<1|1;
        str[0]='$';
        str[1]='#';
        for (int i=1; i<=n; ++i)
        {
            str[i<<1]=s[i];
            str[i<<1|1]='#';
        }
        str[len+1]=0;
        P[1]=1;
        int mid=1,ri=mid+P[mid];
        for (int i=2; i<=len; ++i)
        {
            int j=(i<ri ? min(ri-i,P[mid-(i-mid)]) : 1);
            while(str[i-j]==str[i+j]) ++j;
            P[i]=j;
            if (i+P[i]>ri)
            {
                mid=i;
                ri=mid+P[mid];
            }
        }
    }
    
    int main()
    {
        for (; scanf("%s",s+1)!=EOF; )
        {
            Manacher(s,str,P);
            int ans=0;
            int len=strlen(s+1)<<1|1;
            for (int i=1; i<=len; ++i)
                ans=max(ans,P[i]-1);
            printf("%d\n",ans);
        }
        return 0;
    }
    

    相关文章

      网友评论

          本文标题:hdu 3068 Manacher

          本文链接:https://www.haomeiwen.com/subject/vzlwattx.html