这题是求最长公共子串的长度，用二分求，check mid的时候，把s1的全部长度为mid的子串的hash值存入ihash容器，然后再求依次求出S2的长度为mid的子串的hash值，再用二分查找在ihash里找，找到了说明存在长度为mid的公共子串，找不到就存在。
这题存s1的hash值的时候用数组存就wa，就vector就ac，很奇怪
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<vector>
#include<algorithm>
using namespace std;
#define ull unsigned long long
const int maxn=100000+10;
ull ba[maxn],base=131;
vector<ull>ihash;
string s1,s2;
int len1,len2,ans;
bool check(int len)
{
ihash.clear();
ull tmp=0;
for(int i=1;i<=len;i++)//求出s1里全部长度为len的子串的hash值
{
tmp=tmp*base+s1[i];
}
ihash.push_back(tmp);
for(int i=2;i<=len1-len+1;i++)//求出s1里全部长度为len的子串的hash值
{
tmp=(tmp-s1[i-1]*ba[len-1])*base+s1[i+len-1];
ihash.push_back(tmp);
}
sort(ihash.begin(),ihash.end());//为后面二分查找做准备
//cout<<"s1 ihash："<<endl;
//for(int i=0;i<tot;i++)
//cout<<ihash[i]<<" ";
tmp=0;
for(int i=1;i<=len;i++)//求出s2里全部长度为len的子串的hash值
{
tmp=tmp*base+s2[i];
}
//cout<<"s2 ihash:"<<endl;
//cout<<tmp<<" ";
if(binary_search(ihash.begin(),ihash.end(),tmp))
{
//cout<<"find:"<<tmp<<endl;
return true;
}
for(int i=2;i<=len2-len+1;i++)
{
tmp=(tmp-s2[i-1]*ba[len-1])*base+s2[i+len-1];
//cout<<tmp<<" ";
if(binary_search(ihash.begin(),ihash.end(),tmp))
{
// cout<<"find:"<<tmp<<endl;
return true;
}
}
return false;
}
int main()
{
cin>>s1>>s2;
len1=s1.size();
len2=s2.size();
//cout<<s1<<endl<<s2<<endl<<len1<<" "<<len2<<endl;
s1=" "+s1;
s2=" "+s2;
int low=0,up=min(len1,len2),mid;
ba[0]=1;
for(int i=1;i<=up;i++)
ba[i]=ba[i-1]*base;
ans=-1;
while(low<=up)
{
mid=(low+up)>>1;
//cout<<"mid:"<<mid<<" low:"<<low<<" up:"<<up<<endl;
if(check(mid))
{
ans=mid;
low=mid+1;
}
else
up=mid-1;
//system("pause");
}
cout<<ans<<endl;
return 0;
}