这还是一道数论题
TimeLimit:4000MS MemoryLimit:128MB
64-bit integer IO format:%lld
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%的数据答案为奇数哦
因为没有处理掉字符串尾巴上多余的' ',所以为了防止读到' ' 推荐使用scanf("%s");
Output
输出C的长度
SampleInput
bbabbbcbcbbbddde bbbabbbccadddbbba dggdgzz dggdbb aaa bbb acbdbca bcadacb
SampleOutput
5 4 0 1
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
",ans);
}
return 0;
}