没想到这道题是多组数据，把自己给WA没了...
这道题出现了个问题到现在还没解决，就是写的二分没过...
使用哈希+二分，时间复杂度为O(Nlogn)，思路就是二分长度，然后开始枚举判断，将该长度的所有子串的哈希值放入一个数组中，排好序。然后再在另一个串中开始进行该长度的匹配，如果能匹配上，那么就可以扩大范围，反之则缩小范围。
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1e5 + 10;
const int MOD = 1e9 + 7;
typedef unsigned long long ull;
ull h1[N], h2[N], power[N];
char s1[N], s2[N];
int base = 13331, lens1, lens2;
ull get_hash(ull *h, int s, int e){
return h[e] - h[s - 1] * power[e - s + 1];
}
bool check(int len){
vector<ull> vec;
for(int i = len; i <= lens1; i ++){
ull temp = get_hash(h1, i - len + 1, i);//h1[i] - h1[i - len] * power[i - len + 1];
vec.push_back(temp);
}
sort(vec.begin(), vec.end());
for(int i = len; i <= lens2; i ++){
ull temp = get_hash(h2, i - len + 1, i);
if(binary_search(vec.begin(), vec.end(), temp))
return true;
}
return false;
}
int main(){
while(cin >> s1 + 1 >> s2 + 1){
lens1 = strlen(s1 + 1);
lens2 = strlen(s2 + 1);
h1[0] = h2[0] = 0;
power[0] = 1;
for(int i = 1; i < N; i ++)
power[i] = power[i - 1] * base;
for(int i = 1; i <= lens1; i ++)
h1[i] = h1[i - 1] * base + s1[i];
for(int i = 1; i <= lens2; i ++)
h2[i] = h2[i - 1] * base + s2[i];
int len = min(lens1, lens2);
//错误代码
/*int l = 1, r = len;
while(l < r){
int mid = (l + r + 1) >> 1;
if(check(mid))
l = mid;
else
r = mid - 1;
}
cout << l << endl;*/
int lf = 1, mid, ans = 0;
int rt = min(lens1, lens2);
while(lf <= rt)
{
mid = (lf+rt)/2;
if(check(mid))
{
ans = mid;
lf = mid+1;
}
else
{
rt = mid-1;
}
}
printf("%d
",ans);
}
return 0;
}