https://wenku.baidu.com/view/ed1be61e10a6f524ccbf85fd.html
题意：求两个串的最长公共子串
思路：在求出height数组之后，再把sa数组区分出来，只要其中一个sa[i] (s[i -1])数组是属于第一串，s[i - 1] (s[i])属于第二串，那么我们可以求得其最大值，之所以可以这样做，是因为sa数组已经对字符串按字典序排好序了
#include <iostream> #include <stdio.h> #include <string.h> using namespace std; const int maxn = 2e6 + 5; char s1[maxn], s2[maxn], s[maxn]; int n, p1, p2, m, p; int tx[maxn], sa[maxn], rak[maxn]; int height[maxn]; struct node { int x, y, id; }a[maxn], b[maxn]; void rsort() { for (int i = 1; i <= m; i++) { tx[i] = 0; } for (int i = 1; i <= n; i++) { tx[a[i].y]++; } for (int i = 1; i <= m; i++) { tx[i] += tx[i - 1]; } for (int i = 1; i <= n; i++) { b[tx[a[i].y]--] = a[i]; } for (int i = 1; i <= m; i++) { tx[i] = 0; } for (int i = 1; i <= n; i++) { tx[b[i].x]++; } for (int i = 1; i <= m; i++) { tx[i] += tx[i - 1]; } for (int i = n; i >= 1; i--) { a[tx[b[i].x]--] = b[i]; } } void solve() { rsort(); p = 0; for (int i = 1; i <= n; i++) { if (a[i].x == a[i - 1].x && a[i].y == a[i - 1].y) { rak[a[i].id] = p; } else { rak[a[i].id] = ++p; } } for (int i = 1; i <= n; i++) { a[i].x = rak[i]; a[i].id = sa[rak[i]] = i; a[i].y = 0; } m = p; } void ssort() { m = 127; for (int i = 1; i <= n; i++) { a[i].x = a[i].y = s[i]; a[i].id = i; } solve(); for (int j = 1; j <= n; j <<= 1) { for (int i = 1; i + j <= n; i++) { a[i].y = a[i + j].x; } solve(); if (p == n) { break; } } } void get_Height() { int k = 0; for (int i = 1; i <= n; i++) { if (k) { k--; } int j = sa[rak[i] - 1]; while (s[i + k] == s[j + k]) { k++; } height[rak[i]] = k; } } int main() { scanf("%s", s1 + 1); scanf("%s", s2 + 1); p1 = strlen(s1 + 1); p2 = strlen(s2 + 1); for (int i = 1; i <= p1; i++) { s[++n] = s1[i]; } s[++n] = '#'; for (int i = 1; i <= p2; i++) { s[++n] = s2[i]; } ssort(); get_Height(); int ans = 0; for (int i = 2; i <= n; i++) { if (height[i] > ans) { if ((sa[i] < p1 && sa[i - 1] > p1) || (sa[i] > p1 && sa[i - 1] < p1)) { ans = height[i]; } } } printf("%d\n", ans); return 0; }
