[poj3974] Palindrome 解题报告 （hash\manacher）

题目链接：http://poj.org/problem?id=3974

题目：

多组询问，每组给出一个字符串，求该字符串最长回文串的长度

数据范围支持$O(nlog n)$

解法一：

二分+hash

回文串分奇数串和偶数串。对于奇数串，我们枚举它的中点，二分一下这个中点可以向两边扩展多远的距离；对于偶数串，我们枚举它中间两个点靠左的点，同样二分可以扩展的距离，这样时间复杂度就是$O(nlog n)$的了

说起来容易，写起来不是很容易

解法二：

每次跑一遍manacher就好了

说起来容易，写起来也很容易

解法一代码：

#include<algorithm>

#include<cstring>

#include<iostream>

#include<cstdio>

typedef unsigned long long ull;

using std::string;

using std::cin;

using std::max;

using std::min;

const int N=1e6+;

int cas,ans;

ull p[N],f[N],d[N];

string ch;

int main()

{

    p[]=;

    for (int i=;i<=N;i++) p[i]=p[i-]*;

    while (cin>>ch)

    {

        if (ch=="END") break;

        printf("Case %d: ",++cas);

        memset(f,,sizeof(f));

        memset(d,,sizeof(d));

        int n=ch.size();

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

        {

            f[i+]=f[i]*+ch[i]-'a'+;

        }

        for (int i=n;i>=;i--)

        {

            d[i]=d[i+]*+ch[i-]-'a'+;

        }

        ans=;

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

        {

            int l=,r=min(i,n-i+);

            while (l<r)

            {

                int mid=l+r>>;

                int L1=i-mid+,R1=i;

                int L2=i,R2=i+mid-;

                int tmp1=f[R1]-f[L1-]*p[R1-L1+],tmp2=d[L2]-d[R2+]*p[R2-L2+];

                if (tmp1==tmp2) l=mid+;

                else r=mid;

            }

            int L1=i-l+,R1=i;

            int L2=i,R2=i+l-;

            int tmp1=f[R1]-f[L1-]*p[R1-L1+],tmp2=d[L2]-d[R2+]*p[R2-L2+];

            if (tmp1!=tmp2) l--;

            ans=max(ans,*l-);

            l=,r=min(i,n-i);

            while (l<r)

            {

                int mid=l+r>>;

                int L1=i-mid+,R1=i;

                int L2=i+,R2=i++mid-;

                int tmp1=f[R1]-f[L1-]*p[R1-L1+],tmp2=d[L2]-d[R2+]*p[R2-L2+];

                if (tmp1==tmp2) l=mid+;

                else r=mid;

            }

            L1=i-l+,R1=i;

            L2=i+,R2=i++l-;

            tmp1=f[R1]-f[L1-]*p[R1-L1+],tmp2=d[L2]-d[R2+]*p[R2-L2+];

            if (tmp1!=tmp2) l--;

            ans=max(ans,*l);

        }

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

    }

    return ;

}

解法二代码：

#include<algorithm>

#include<cstdio>

#include<cstring>

#include<iostream>

const int N=2e6+;

using std::string;

using std::cin;

using std::min;

using std::max;

string ch;

char s[N];

int hw[N];

int main()

{

    int cas=;

    while (cin>>ch)

    {

        if (ch=="END") return ;

        printf("Case %d: ",++cas);

        int n=ch.size();

        memset(hw,,sizeof(hw));

        s[]=s[]='#';

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

        {

            s[i<<]=ch[i-];

            s[i<<|]='#';

        }

        n=n*+;

        s[n]=;

        int mx=,mid;

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

        {

            if (i<mx) hw[i]=min(mid+hw[mid]-i,hw[(mid<<)-i]);

            else hw[i]=;

            for (;s[i+hw[i]]==s[i-hw[i]];hw[i]++);

            if (hw[i]+i>mx)

            {

                mx=hw[i]+i;

                mid=i;

            }

        }

        int ans=;

        for (int i=;i<n;i++) ans=max(ans,hw[i]);

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

    }

    return ;

}