POJ 2774 Long Long Message：後綴數組求最長公共子串

問題描述

給定兩個長度 ≤ 100000 的小寫字母字符串。求最長公共子串長度。

後綴數組解法

1. 將兩串連接：S = A + '#' + B（# 為不在字母表中字符，ASCII 值小於 'a'）。
2. 構建 S 的後綴數組 SA 和 Height 數組（Height[i] = LCP(SA[i], SA[i-1])）。
3. 遍歷 Height，若 SA[i] 和 SA[i-1] 分屬不同原串（一個 < |A|，一個 > |A|），則 Height[i] 為候選答案。取最大值。

代碼核心（倍增法構建 SA）

#define MAXN 222222
int wa[MAXN], wb[MAXN], wv[MAXN], ws[MAXN];
int sa[MAXN], height[MAXN], rank[MAXN];
char str[MAXN*2];
int r[MAXN*2];

void da(int n, int m) { // n=長度, m=字符集大小
    int i, j, p, *x=wa, *y=wb, *t;
    for(i=0;i=0;i--) sa[--ws[x[i]]]=i;
    for(j=1,p=1;p=j) y[p++]=sa[i]-j;
        for(i=0;i=0;i--) sa[--ws[wv[i]]]=y[i];
        t=x; x=y; y=t;
        p=1; x[sa[0]]=0;
        for(i=1;i=n) break;
    }
}
void build_height(int n) {
    for(i=0;i

int ans = 0;
int len1 = strlen(A);
for (int i = 1; i < n; i++) {
    if (height[i] > ans) {
        if ((sa[i-1] < len1 && sa[i] > len1) || (sa[i] < len1 && sa[i-1] > len1))
            ans = height[i];
    }
}
printf("%d\n", ans);