求两串的最长相同公共连续子串
将两串拼接在一起，中间用一个未出现过的符号隔开
求 sa, height
sa[i] 与 sa[i-1] 不在同一个串时的 height[i] 的最大值就是答案
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 const int MAXN = 200005; 6 7 struct SuffixArray 8 { 9 int wa[MAXN], wb[MAXN], wsf[MAXN], wv[MAXN]; 10 int Cmp(int r[], int a, int b, int k) 11 { 12 return r[a] == r[b] && r[a+k] == r[b+k]; 13 } 14 void GetSa(int r[], int sa[], int n, int m) 15 { 16 int i, j, p, *x = wa, *y = wb, *t; 17 for (i = 0; i < m; i++) wsf[i] = 0; 18 for (i = 0; i < n; i++) wsf[x[i]=r[i]]++; 19 for (i = 1; i < m; i++) wsf[i] += wsf[i-1]; 20 for (i = n - 1; i >= 0; i--) sa[--wsf[x[i]]] = i; 21 for (p = j = 1; p < n; j *= 2, m = p) 22 { 23 for (p = 0, i = n - j; i < n; i++) y[p++] = i; 24 for (i = 0; i < n; i++) if(sa[i] >= j) y[p++] = sa[i] - j; 25 for (i = 0; i < n; i++) wv[i] = x[y[i]]; 26 for (i = 0; i < m; i++) wsf[i] = 0; 27 for (i = 0; i < n; i++) wsf[wv[i]]++; 28 for (i = 1; i < m; i++) wsf[i] += wsf[i-1]; 29 for (i = n-1; i >= 0; i--) sa[--wsf[wv[i]]] = y[i]; 30 swap(x, y); 31 x[sa[0]] = 0; 32 for (p = i = 1; i < n; i++) 33 x[sa[i]] = Cmp(y, sa[i-1], sa[i], j) ? p - 1: p++; 34 } 35 } 36 void GetHeight(int r[], int sa[], int rnk[], int height[], int n) 37 { 38 int i, j, k = 0; 39 for (i = 1; i <= n; i++) 40 rnk[sa[i]] = i; 41 for (i = 0; i < n; i++) 42 { 43 if (k) k--; 44 j = sa[rnk[i]-1]; 45 while (r[i+k] == r[j+k]) k++; 46 height[rnk[i]] = k; 47 } 48 } 49 50 }suffixArray; 51 int r[MAXN], sa[MAXN], rnk[MAXN], height[MAXN]; 52 char s[MAXN]; 53 int len1, len2; 54 bool check(int i, int j) 55 { 56 return ( sa[i] < len1 && sa[j] > len1 ) || 57 ( sa[i] > len1 && sa[j] < len1 ) ; 58 } 59 int main() 60 { 61 scanf("%s",s); 62 len1 = strlen(s); 63 s[len1] = '#'; 64 scanf("%s", s + len1 + 1); 65 len2 = strlen(s); 66 int m = 0; 67 for (int i = 0; i < len2; i++) 68 { 69 if(i == len1) r[i] = 1; 70 else r[i] = s[i] - 'a' + 2; 71 m = max(r[i] + 1, m); 72 } 73 r[len2] = 0; 74 suffixArray.GetSa(r, sa, len2 + 1, m); 75 suffixArray.GetHeight(r, sa, rnk, height, len2); 76 int ans = 0; 77 for (int i = 1; i < len2; i++) 78 { 79 if(check(i,i-1)) 80 { 81 ans = max(height[i], ans); 82 } 83 } 84 printf("%d ", ans); 85 }