HDU 4117 GRE Words 題解：後綴數組 + DP 求最大權值單詞鏈

題目大意

給定 N 個單詞，每個單詞有權值。需選擇一個單詞序列，使得**前一個單詞是後一個單詞的子串**。最大化所選單詞權值之和。輸出最大和。

約束：數據規模允許後綴數組 O(L²) 或 O(L² log L) 通過 (L 為總長度)。

核心思路：後綴數組判斷子串關係 + DP 轉移

1. 拼接所有單詞：用唯一分隔符 (如 i+128) 連接，構成總串 S。
2. 構建後綴數組 SA：倍增算法 O(L log L) 構建。
3. 計算 Height 數組：Kasai 算法 O(L) 獲取相鄰後綴 LCP。
4. DP 狀態：dp[i] 表示以第 i 個單詞結尾的最大權值和。初始 dp[i] = val[i]。
5. 轉移：對每個單詞 i，在 SA 中找到其所有後綴的位置區間。利用 Height 數組向左右擴展，找到所有以單詞 i 為前綴的後綴。若該後綴屬於單詞 j (j > i)，則 dp[j] = max(dp[j], dp[i] + val[j])。
6. 答案：max(dp[1..N])。

關鍵技術細節

1. 後綴屬於哪個單詞

構建 SA 時同步記錄 bel[pos] = 該後綴起始位置屬於第幾個單詞 (0 表示分隔符)。

2. 高效枚舉以單詞 i 為前綴的所有後綴

單詞 i 在總串中的起始位置為 st[i]，長度 sumlen[i]。在 SA 中其排名為 rank[st[i]]。
向右掃描：mlen = min(mlen, height[k])，若 mlen >= sumlen[i] 且 bel[sa[k]] > i，則單詞 bel[sa[k]] 以單詞 i 為前綴 (即單詞 i 是其子串)。
向左同理。

3. 剪枝優化

if (mlen < sumlen[i]) break; — 一旦公共前綴長度小於單詞 i 長度，後續後綴不可能以 i 為前綴。

完整 AC 代碼 (C++)

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

const int MAXN = 350005;
const int INF = 0x3f3f3f3f;

int str[MAXN];      // 總串 (整數編碼)
int sa[MAXN], rk[MAXN], ht[MAXN];
int t1[MAXN], t2[MAXN], c[MAXN];
int bel[MAXN];      // 後綴屬於哪個單詞
int st[MAXN];       // 單詞在總串中的起始位置
int sumlen[MAXN];   // 單詞長度
int val[MAXN];      // 單詞權值
int dp[MAXN];       // DP 陣列

void build_sa(int n, int m) { // n=總長度, m=字符集大小
    int *x = t1, *y = t2;
    for (int i = 0; i < m; ++i) c[i] = 0;
    for (int i = 0; i < n; ++i) c[x[i] = str[i]]++;
    for (int i = 1; i < m; ++i) c[i] += c[i-1];
    for (int i = n-1; i >= 0; --i) sa[--c[x[i]]] = i;
    for (int k = 1; k <= n; k <<= 1) {
        int p = 0;
        for (int i = n-k; i < n; ++i) y[p++] = i;
        for (int i = 0; i < n; ++i) if (sa[i] >= k) y[p++] = sa[i] - k;
        for (int i = 0; i < m; ++i) c[i] = 0;
        for (int i = 0; i < n; ++i) c[x[y[i]]]++;
        for (int i = 1; i < m; ++i) c[i] += c[i-1];
        for (int i = n-1; i >= 0; --i) sa[--c[x[y[i]]]] = y[i];
        swap(x, y);
        p = 1; x[sa[0]] = 0;
        for (int i = 1; i < n; ++i)
            x[sa[i]] = (y[sa[i-1]] == y[sa[i]] && y[sa[i-1]+k] == y[sa[i]+k]) ? p-1 : p++;
        if (p >= n) break;
        m = p;
    }
}

void get_height(int n) {
    for (int i = 0; i < n; ++i) rk[sa[i]] = i;
    int k = 0;
    for (int i = 0; i < n; ++i) {
        if (k) --k;
        if (rk[i] == 0) continue;
        int j = sa[rk[i]-1];
        while (str[i+k] == str[j+k]) ++k;
        ht[rk[i]] = k;
    }
}

int main() {
    int T; scanf("%d", &T);
    for (int cas = 1; cas <= T; ++cas) {
        int N; scanf("%d", &N);
        int n = 0; // 總串長度
        for (int i = 1; i <= N; ++i) {
            char tmp[100005]; // 單詞最大長度
            scanf("%s%d", tmp, &val[i]);
            dp[i] = val[i];
            int len = strlen(tmp);
            st[i] = n;
            sumlen[i] = len;
            for (int j = 0; j < len; ++j) {
                str[n] = tmp[j];
                bel[n++] = i;
            }
            bel[n] = i; // 分隔符也屬於該單詞 (便於邊界處理)
            str[n++] = i + 128; // 唯一分隔符 (ASCII 128+)
        }
        str[n-1] = 0; // 結束符
        build_sa(n, 30000); // 字符集上界
        get_height(n);

        for (int i = 1; i <= N; ++i) {
            int mlen = INF;
            // 向右擴展
            for (int j = rk[st[i]] + 1; j < n; ++j) {
                mlen = min(mlen, ht[j]);
                if (mlen < sumlen[i]) break;
                if (bel[sa[j]] > i)
                    dp[bel[sa[j]]] = max(dp[bel[sa[j]]], val[bel[sa[j]]] + dp[i]);
            }
            mlen = INF;
            // 向左擴展
            for (int j = rk[st[i]] - 1; j > 0; --j) {
                mlen = min(mlen, ht[j+1]);
                if (mlen < sumlen[i]) break;
                if (bel[sa[j]] > i)
                    dp[bel[sa[j]]] = max(dp[bel[sa[j]]], val[bel[sa[j]]] + dp[i]);
            }
        }
        int ans = 0;
        for (int i = 1; i <= N; ++i) ans = max(ans, dp[i]);
        printf("Case #%d: %d\n", cas, ans);
    }
    return 0;
}

複雜度分析

• 構建 SA：O(L log L) (倍增算法)，L = 總長度 ≤ 35萬。
• Height 計算：O(L)。
• DP 掃描：每個單詞向左右掃描 SA，最壞 O(L) 每詞，總 O(N·L)。但剪枝極強，實測極快。數據水題目可過。
• 空間：O(L)。

避坑指南

1. 分隔符必須唯一且不在字符集中：用 i+128 保證每個單詞分隔符不同，避免跨單詞偽匹配。
2. bel 數組大小：需覆蓋總串所有位置，包括分隔符位置。
3. DP 更新順序**：外層循環 i=1..N 保證轉移來源 dp[i] 已計算完畢 (拓撲序)。
4. 答案取 max(dp) 而非 dp[N]**：最優鏈不一定以最後一個單詞結尾。

結語

HDU 4117 是後綴數組結合 DP 的經典應用。核心洞見：**後綴數組的有序特性使得「某串是否為另一串子串」轉化為「在 SA 中相鄰區間的 LCP 查詢」**。雖理論複雜度非最優，但倍增 SA + Kasai Height + 區間掃描 DP 的工程實現簡潔高效，是字符串問題「快速 AC」的利器。