题目链接：
题目分析
题目要求求出两个字符串的最长公共子串，使用后缀数组求解会十分容易。
将两个字符串用特殊字符隔开再连接到一起，求出后缀数组。
可以看出，最长公共子串就是两个字符串分别的一个后缀的 LCP ，并且这两个后缀在 SA 中一定是相邻的。
那么他们的 LCP 就是 Height[i] ，当然，Height[i] 的最大值不一定就是 LCS ，因为可能 SA[i] 和 SA[i-1] 是在同一个字符串中。
那么判断一下，如果 SA[i] 与 SA[i - 1] 分别在两个字符串中，就用 Height[i] 更新 Ans 。
代码
#include#include #include #include #include #include using namespace std;const int MaxL = 200000 + 15;int n, l1, l2, Ans;int A[MaxL], Rank[MaxL], Height[MaxL], SA[MaxL];int VA[MaxL], VB[MaxL], VC[MaxL], Sum[MaxL];char S1[MaxL], S2[MaxL];inline bool Cmp(int *a, int x, int y, int l) { return (a[x] == a[y]) && (a[x + l] == a[y + l]);}void DA(int *A, int n, int m) { int *x, *y, *t; x = VA; y = VB; for (int i = 1; i <= m; ++i) Sum[i] = 0; for (int i = 1; i <= n; ++i) ++Sum[x[i] = A[i]]; for (int i = 2; i <= m; ++i) Sum[i] += Sum[i - 1]; for (int i = n; i >= 1; --i) SA[Sum[x[i]]--] = i; int p, q; p = 0; for (int j = 1; p < n; j <<= 1, m = p) { q = 0; for (int i = n - j + 1; i <= n; ++i) y[++q] = i; for (int i = 1; i <= n; ++i) { if (SA[i] <= j) continue; y[++q] = SA[i] - j; } for (int i = 1; i <= n; ++i) VC[i] = x[y[i]]; for (int i = 1; i <= m; ++i) Sum[i] = 0; for (int i = 1; i <= n; ++i) ++Sum[VC[i]]; for (int i = 2; i <= m; ++i) Sum[i] += Sum[i - 1]; for (int i = n; i >= 1; --i) SA[Sum[VC[i]]--] = y[i]; t = x; x = y; y = t; x[SA[1]] = 1; p = 1; for (int i = 2; i <= n; ++i) x[SA[i]] = Cmp(y, SA[i], SA[i - 1], j) ? p : ++p; } for (int i = 1; i <= n; ++i) Rank[SA[i]] = i; //GetHeight int h, o; h = 0; for (int i = 1; i <= n; ++i) { if (Rank[i] == 1) continue; o = SA[Rank[i] - 1]; while (A[i + h] == A[o + h]) ++h; Height[Rank[i]] = h; if (h > 0) --h; } }int main() { scanf("%s%s", S1 + 1, S2 + 1); l1 = strlen(S1 + 1); l2 = strlen(S2 + 1); for (int i = 1; i <= l1; ++i) A[i] = S1[i] - 'a' + 1; A[l1 + 1] = 27; for (int i = 1; i <= l2; ++i) A[l1 + 1 + i] = S2[i] - 'a' + 1; A[l1 + 1 + l2 + 1] = 28; n = l1 + 1 + l2 + 1; DA(A, n, 28); Ans = 0; for (int i = 2; i <= n - 1; ++i) { if (Height[i] > Ans) { if (SA[i] <= l1 && SA[i - 1] > l1 + 1) Ans = Height[i]; if (SA[i] > l1 + 1 && SA[i - 1] <= l1) Ans = Height[i]; } } printf("%d\n", Ans); return 0;}