求两串的最长相同公共连续子串
将两串拼接在一起，中间用一个未出现过的符号隔开
求 sa, height
sa[i] 与 sa[i-1] 不在同一个串时的 height[i] 的最大值就是答案
1 #include2 #include 3 #include 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\n", ans);85 }