Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 字符串哈希 + 2 * 二分查找 = 400题留念~~~

Posted by vjubge4 at 2019-06-06 21:35:07 on Problem 2774
```#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef unsigned long long ull;
ull F1[100001], F2[100001];
int L1, L2;
ull Base[100001];
char str1[100001], str2[100001];
const ull B = 19;
ull temp[100001];
bool Judge(int mid) {
int C = 0;
for(int l = 0, r = l + mid; r <= L2; l ++, r ++) {
ull t = F2[r] - F2[l] * Base[mid];
temp[C ++] = t;
}
sort(temp, temp + C);
for(int i = 0, j = i + mid; j <= L1; i ++, j ++) {
ull t = F1[j] - F1[i] * Base[mid];
ull * rt = lower_bound(temp, temp + C, t);
if(rt - temp < C && *rt == t){
return true;
}
}
return false;
}

int main() {
Base[0] = 1;
for(int i = 1; i <= 100000; i ++) {
Base[i] = Base[i - 1] * B;
}
gets(str1);
gets(str2);
L1 = strlen(str1);
L2 = strlen(str2);
F1[0] = 0;
for(int i = 1; i <= L1; i ++) {
F1[i] = F1[i - 1] * B + str1[i - 1];
}
F2[0] = 0;
for(int i = 1; i <= L2; i ++) {
F2[i] = F2[i - 1] * B + str2[i - 1];
}
int lb = 0, ub = L1;
int ans = 0;
while(ub >= lb) {
int mid = (ub + lb) >> 1;
if(Judge(mid)) {
ans = mid;
lb = mid + 1;
} else {
ub = mid - 1;
}
}
printf("%d\n", ans);
}
```

Followed by: