HDU 5384 Danganronpa：AC 自動機多模式匹配統計

題目大意

• n 個文本串 A_i（總長 ≤ 1e5），m 個模式串 B_j（總長 ≤ 1e5）。
• 對每個 A_i，輸出所有 B_j 在其出現次數之和（模式串可重疊）。
• 多測試用例，總長 ≤ 6e5。

AC 自動機（Aho-Corasick）

1. 將所有模式串 B_j 插入 Trie，節點存 `end` = 以此節點結尾的模式串數（可重複）。
2. BFS 構建 `fail` 指針：`fail[u]` 為最長真後綴對應的節點。
3. 構建轉移表 `go[u][c]`（或查詢時沿 `fail` 跳轉）。

查詢統計

對每個文本 A_i 走自動機，每步沿 `fail` 鏈累加 `end`（或預先在構建時將 `end` 累加到 `fail` 所指節點，查詢時只需加當前節點 `end`）。

完整代碼

#include 
using namespace std;
const int MAXN = 600005;
struct Node { int nxt[26], fail, end; } trie[MAXN];
int nodeCnt;

int newNode() {
    memset(trie[nodeCnt].nxt, -1, sizeof(trie[nodeCnt].nxt));
    trie[nodeCnt].fail = 0;
    trie[nodeCnt].end = 0;
    return nodeCnt++;
}

void insert(const string& s) {
    int u = 0;
    for (char ch : s) {
        int c = ch - 'a';
        if (trie[u].nxt[c] == -1) trie[u].nxt[c] = newNode();
        u = trie[u].nxt[c];
    }
    trie[u].end++;
}

void buildFail() {
    queue q;
    for (int c = 0; c < 26; ++c) {
        int v = trie[0].nxt[c];
        if (v != -1) { trie[v].fail = 0; q.push(v); }
        else trie[0].nxt[c] = 0;
    }
    while (!q.empty()) {
        int u = q.front(); q.pop();
        trie[u].end += trie[trie[u].fail].end; // 累加 fail 鏈的 end
        for (int c = 0; c < 26; ++c) {
            int v = trie[u].nxt[c];
            if (v != -1) {
                trie[v].fail = trie[trie[u].fail].nxt[c];
                q.push(v);
            } else {
                trie[u].nxt[c] = trie[trie[u].fail].nxt[c];
            }
        }
    }
}

long long query(const string& s) {
    long long ans = 0;
    int u = 0;
    for (char ch : s) {
        u = trie[u].nxt[ch - 'a'];
        ans += trie[u].end;
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        nodeCnt = 0; newNode(); // root = 0
        int n, m; cin >> n >> m;
        vector A(n), B(m);
        for (int i = 0; i < n; ++i) cin >> A[i];
        for (int j = 0; j < m; ++j) {
            cin >> B[j];
            insert(B[j]);
        }
        buildFail();
        for (int i = 0; i < n; ++i)
            cout << query(A[i]) << "\n";
    }
    return 0;
}

複雜度

• 構建 Trie + Fail：O(總模式長 × 字母表) ≈ 2.6M 操作。
• 查詢：O(總文本長)。
• 總體線性，記憶體 O(節點數 × 26) ≈ 600k × 26 × 4B ≈ 62MB，可接受。