HDU 3336 Count the string：KMP Next 數組應用統計前綴出現次數

問題大意

給定長度為 len 的字符串 s，求所有前綴在 s 中出現的次數之和（模 10007）。例如 s = "ababa"，前綴 "a" 出現 3 次，"ab" 出現 2 次，"aba" 出現 2 次，"abab" 出現 1 次，"ababa" 出現 1 次，總和 = 9。

KMP Next 數組性質

Next[i] 表示前綴 s[0..i-1] 的最長真前綴同時也是後綴的長度。若 Next[i] = k，則長度為 k 的前綴在以 i-1 結尾的子串中出現。遞推關係：每個位置 i 對應的前綴長度為 i，它同時也是所有 Next 鏈上的長度的前綴的後綴。

統計方法

1. 計算 Next 數組（標準 KMP 預處理）。
2. 初始化 cnt[i] = 1（每個前綴至少出現一次，即自身）。
3. 對每個 i 從 1 到 len，沿 Next 鏈向前跳轉：t = Next[i]; while (t > 0) { cnt[t-1]++; t = Next[t]; }
4. 答案 = Σ cnt[i] (mod 10007)。

代碼實現

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200010;
const int MOD = 10007;
int Next[MAXN], cnt[MAXN];
char s[MAXN];

void get_next(int len) {
    int i = 0, j = Next[0] = -1;
    while (i < len) {
        while (j != -1 && s[i] != s[j]) j = Next[j];
        Next[++i] = ++j;
    }
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int len; scanf("%d", &len);
        scanf("%s", s);
        get_next(len);
        fill(cnt, cnt + len + 1, 1);
        for (int i = 1; i <= len; ++i) {
            int t = Next[i];
            while (t > 0) {
                cnt[t-1] = (cnt[t-1] + 1) % MOD;
                t = Next[t];
            }
        }
        int ans = 0;
        for (int i = 0; i < len; ++i) ans = (ans + cnt[i]) % MOD;
        printf("%d\n", ans);
    }
    return 0;
}

複雜度分析

Next 數組構建 O(len)，統計過程中每個位置沿 Next 鏈跳轉，總跳轉次數 O(len)（類似 KMP 匹配分析），總時間 O(len)，空間 O(len)。

關鍵點提示

• Next 數組下標定義要與統計邏輯對應（代碼中 Next[i] 對應長度 i 的前綴）。
• 模數較小，注意取模。
• 可進一步優化：構建失敗樹，DFS 累加子樹大小，但鏈式跳轉已足夠快。