题意：给出s，t两个字符串，求最长公共子串的长度
思路：首先二分答案x，预处理出s中长度为x的子串哈希值并排序，在t中枚举起点，二分查找t[i...i+x]的哈希值
二分查找直接用binary_search（）函数
复杂度其实是nlog方
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<iostream> 5 #define LL long long 6 #define uLL unsigned long long 7 #define debug(x) cout << "[" << x << "]" << endl 8 using namespace std; 9 10 const int mx = 1e5+10; 11 const int base = 131; 12 char s[mx], t[mx]; 13 uLL hs[mx], ht[mx], a[mx], p[mx]; 14 int n, m; 15 16 bool check(int x){ 17 int cnt = 0; 18 for (int i = x; i <= n; i++) 19 a[cnt++] = hs[i]-p[x]*hs[i-x]; 20 sort(a, a+cnt); 21 for (int i = x; i <= m; i++){ 22 uLL k = ht[i]-p[x]*ht[i-x]; 23 if (binary_search(a, a+cnt, k)) return 0; 24 } 25 return 1; 26 } 27 28 int main(){ 29 p[0] = 1; 30 scanf("%s%s", s+1, t+1); 31 n = strlen(s+1), m = strlen(t+1); 32 for (int i = 1; i <= n; i++) hs[i] = hs[i-1]*base+s[i]-'a'; 33 for (int i = 1; i <= m; i++) ht[i] = ht[i-1]*base+t[i]-'a'; 34 for (int i = 1; i <= max(n, m); i++) p[i] = p[i-1]*base; 35 int l = 0, r = min(n, m); 36 while (l <= r){ 37 int mid = (l+r)>>1; 38 if (check(mid)) r = mid-1; 39 else l = mid+1; 40 } 41 printf("%d ", r); 42 return 0; 43 }