SPOJ 694 DISUBSTR: 不同子串計數 - 後綴陣列 + LCP 陣列解法

題目大意

給定字串長度 ≤ 1000，測資 ≤ 20 組，求**不同子串總數**。

數學關係

• 所有子串 = 所有後綴的前綴集合。
• 第 i 個後綴 (SA[i]) 長度為 n - SA[i]，貢獻 n - SA[i] 個前綴（即子串）。
• 但相鄰後綴有共同前綴，長度為 LCP[i] = height[i]，需扣除。
• 總不同子串數 = Σ (n - SA[i] - height[i])，i = 0..n-1，其中 height[0] = 0。

演算法流程

1. 構建後綴陣列 SA（倍增法 O(n log n) 或 DC3 O(n)）。
2. 由 SA 構建 rank 陣列，再用 Kasai 算法 O(n) 求 height (LCP) 陣列。
3. 套用公式累加答案。

完整 C++ 實作 (倍增法 SA + Kasai LCP)

#include 
using namespace std;

const int MAXN = 10005;
int sa[MAXN], rk[MAXN], rk2[MAXN], ht[MAXN], cnt[MAXN], *x, *y;
char str[MAXN];

bool equal_sub(int *r, int a, int b, int l) {
    return r[a]==r[b] && a+l=0; --i) sa[--cnt[x[y[i]]]] = y[i];
}

void build_sa(int n, int m=256) {
    x = rk; y = rk2;
    for (int i=0; i=len) y[p++] = sa[i]-len;
        radix_sort(n, m);
        swap(x, y);
        x[sa[0]] = p = 0;
        for (int i=1; i= n) break;
    }
    for (int i=0; i> T;
    while (T--) {
        cin >> str;
        int n = strlen(str);
        build_sa(n);
        build_height(n);
        long long ans = 0;
        for (int i=0; i

輸入:
2
CCCCC
ABABA

輸出:
5
9

說明 ABABA:
長度1: A,B (2)
長度2: AB,BA (2)
長度3: ABA,BAB (2)
長度4: ABAB,BABA (2)
長度5: ABABA (1)
總計 9