Description
求两个串的最长连续公共字串
Solution
后缀数组入门题吧
把两个串连在一起，中间加一个分隔符，然后跑一遍后缀数组，得到 height 和 sa
一个 height[i] 对答案有贡献的充要条件是 sa[i] 和 sa[i-1] 分别在两个串中
Code
#include#include #include #include using namespace std;const int N = 200200;char s1[N], s2[N], S[N];int n, tmpn, cnt[N], ans, sa[N], rk[N], height[N]; struct node { int id, x, y; } a[N], b[N]; int main() { scanf("%s %s", s1, s2); tmpn = strlen(s1); for(int i = 0; s1[i]; i++) S[++n] = s1[i]; S[++n] = '#'; for(int i = 0; s2[i]; i++) S[++n] = s2[i]; for(int i = 1; i <= n; i++) cnt[S[i]] = 1; for(int i = 0; i <= 128; i++) cnt[i] += cnt[i - 1]; for(int i = 1; i <= n; i++) rk[i] = cnt[S[i]]; for(int L = 1; L <= n; L *= 2) { for(int i = 1; i <= n; i++) a[i].id = i, a[i].x = rk[i], a[i].y = rk[i + L]; for(int i = 1; i <= n; i++) cnt[i] = 0; for(int i = 1; i <= n; i++) cnt[a[i].y]++; for(int i = 1; i <= n; i++) cnt[i] += cnt[i - 1]; for(int i = 1; i <= n; i++) b[cnt[a[i].y]--] = a[i]; for(int i = 1; i <= n; i++) cnt[i] = 0; for(int i = 1; i <= n; i++) cnt[a[i].x]++; for(int i = 1; i <= n; i++) cnt[i] += cnt[i - 1]; for(int i = n; i >= 1; i--) a[cnt[b[i].x]--] = b[i]; for(int i = 1; i <= n; i++) if(a[i].x == a[i - 1].x && a[i].y == a[i - 1].y) rk[a[i].id] = rk[a[i - 1].id]; else rk[a[i].id] = rk[a[i - 1].id] + 1; } for(int i = 1; i <= n; i++) sa[rk[i]] = i; int k = 0; for(int i = 1; i <= n; i++) { int j = sa[rk[i] - 1]; if(k) k--; while(i + k <= n && j + k <= n && S[i + k] == S[j + k]) k++; height[rk[i]] = k; } for(int i = 1; i <= n; i++) if(sa[i] <= tmpn && sa[i - 1] > tmpn || sa[i] > tmpn && sa[i - 1] <= tmpn) ans = max(ans, height[i]); printf("%d\n", ans); return 0;}