这还是一道数论题

TimeLimit:4000MS MemoryLimit:128MB

64-bit integer IO format:%lld

Special Judge

Problem Description

最后来个字符串签个到吧，这题其实并不难，所需的算法比较基础，甚至你们最近还上过课。

为了降低难度，免得所有人爆零。这里给几个提示的关键字：字符串，回文，二分，哈希. 注意要对奇偶回文分开二分

这样还不会做，说明基础有所欠缺。

给你一个字符串A和一个字符串B,请你求一个满足以下要求的所有字符串中，最长的字符串C的长度：

C必须同时是A和B的子串，即A和B中都必须存在一个子区间和C长得一样
C必须是一个回文，即正过来读和反过来读都一样

Input

多组数据，请处理到EOF

每组数据包含，两行，每行都是仅由小写字符构成的字符串，代表A和B。

对于30%的数据。

保证|A|,|B|<=1000，且单个文件的字符总数小于10000

对于100%的数据

保证|A|,|B|<=100000，且单个文件的字符总数小于2e6

其中70%的数据答案为奇数哦

因为没有处理掉字符串尾巴上多余的'\r',所以为了防止读到'\r' 推荐使用scanf("%s");

Output

输出C的长度

SampleInput

bbabbbcbcbbbddde

bbbabbbccadddbbba

dggdgzz

dggdbb

aaa

bbb

acbdbca

bcadacb

SampleOutput

hint:

对于第一个数据C取bbabb

对于第二个数据C取dggd

用马拉车预处理，这样可以O(1)判断任意区间是否是回文。 然后就是用二分答案的长度，用哈希O(n)计算是否有长度为len的公
共回文子串，注意。  二分时奇偶回文要分开二分。因为如何有2k+2长度的公共回文。肯定也会有2k长度的公共回文，但是不保证也
有2k+1的长度的公共回文。。数据里70%的答案是奇的。所以你只二分奇数长度即可得到70分. 如果不想奇偶分开讨论的话，可以用马拉车的技巧，转化为全部都是奇回文
细节在代码中有解释

#include<bits/stdc++.h>

typedef unsigned long long ull;

const int maxn=100005;

const ull P=131;

using namespace std;

char str1[maxn],str2[maxn];

ull f1[maxn],f2[maxn],p[maxn];

int len1,len2,tmp_len;

int len[maxn<<1];

char tmp[maxn<<1];

void init()

{

    p[0]=1;

    for(int i=1; i<maxn; i++)

    {

        p[i]=p[i-1]*P;

    }

}

ull Hash(ull f[],int l,int r)

{

    return f[r+1]-f[l]*p[r-l+1];

}

void GetHash(char str[],ull f[])

{

    int len_str=strlen(str);

    f[0]=0;

    for(int i=0; i<len_str; i++)

        f[i+1]=f[i]*P+str[i];

}

int manachar_init(char st[])

{

    int i,str_len=strlen(st);

    tmp[0]='@';///加一个特殊字符，防止越界

    for(int i = 1; i <= 2*str_len ; i+=2)

    {

        tmp[i]='#';

        tmp[i+1]=st[i/2];

    }

    tmp[2*str_len+1]='#';

    tmp[2*str_len+2]='$';///字符串结尾加一个字符，防止越界

    return 2*str_len+1;///返回转换字符串的长度

}

void manachar(char st[],int str_len)

{

    int p_mx=0,ans=0,po=0;///p_mx即为“当前”计算回文串最右边字符的最大值,po为当前该回文字符串的中心

    for(int i=1;i<=str_len;i++)

    {

        if(i<p_mx)

            len[i]=min(p_mx-i,len[2*po-i]);///po对应最大回文子串中心点的位置

        else

            len[i]=1;

            while(st[i-len[i]]==st[i+len[i]])

                len[i]++;

            if(len[i]+i>p_mx)

            {

                po=i;

                p_mx=i+len[i];

            }

        ans=max(ans,len[i]);

    }

}

map< ull,int >mp;

bool cheak(int m)

{

    mp.clear();

    for(int i=0; str1[i+m-1]; i++)

    {

        if(len[i+i+m+1]-1>=m)///i+i+m+1对应原回文子字符串str[i~(i+m-1)]在转换后字符串的回文中心位置（l+r+2）

        {

            ull cnt=Hash(f1,i,i+m-1);

            mp[cnt]=i;///记录该回文串的起点

        }

    }

    for(int i=0; str2[i+m-1]; i++) ///枚举第二个字符串的起点

    {

        ull cnt=Hash(f2,i,i+m-1);

        if(mp.count(cnt))

        {

            int po=mp[cnt];///po为在str1中的起点

            int j=0;

            for( j=0; j<m; j++)///判断这两个字符串是否相等

            {

                if(str1[po+j]!=str2[i+j])

                    break;

            }

            if(j>=m)

                return true;

        }

    }

    return false;

}

int main()

{

    init();

    while(scanf("%s %s",str1,str2)!=EOF)

    {

        int ans=0;

        GetHash(str1,f1);

        GetHash(str2,f2);

        len1=strlen(str1);

        len2=strlen(str2);

        tmp_len=manachar_init(str1);

        ///tmp为转换后的字符串 tmp_len该字符串长度

        manachar(tmp,tmp_len);

        int l=0,r=min(len1,len2)/2+1;

        while(l+1<r)

        {

            int mid=(l+r)/2;

            if(cheak(mid*2))

            {

                l=mid;

            }

            else

            {

                r=mid;

            }

        }

        ans=max(ans,l*2);

        l=l-1,r=min(len1,len2)/2+1;

        while(l+1<r)

        {

            int mid=(l+r)/2;

            if(cheak(mid*2+1))

            {

                l=mid;

            }

            else

            {

                r=mid;

            }

        }

        ans=max(ans,l*2+1);

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

    }

    return 0;

}

是一

FJUT-这还是一道数论题

这还是一道数论题