HDU 2846 Repository：字典樹統計子串出現次數

題目大意

• 給定 P ≤ 10,000 個商品名（小寫字母，長度 ≤ 20）。
• Q ≤ 100,000 次查詢，每次給一個字符串，詢問有多少商品名包含它作為子串。
• 同一商品名中相同子串只計數一次。

Trie + 計數器

1. 對每個商品名，枚舉所有起始位置，將後綴插入字典樹。
2. 每個節點存 id（最後插入該節點的商品編號）和 cnt（經過多少不同商品）。
    插入時若 node.id != 當前商品id，則 node.id = 當前id, node.cnt++。
3. 查詢直接走字典樹，到達節點返回 cnt，中途斷開返回 0。

完整代碼

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

struct Node {
    int id, cnt;
    Node* nxt[26];
    Node() : id(-1), cnt(0) { memset(nxt, 0, sizeof(nxt)); }
} *root;

void insert(const char* s, int idx) {
    int len = strlen(s);
    for (int start = 0; start < len; ++start) {
        Node* p = root;
        for (int i = start; i < len; ++i) {
            int c = s[i] - 'a';
            if (!p->nxt[c]) p->nxt[c] = new Node();
            p = p->nxt[c];
            if (p->id != idx) {
                p->id = idx;
                ++p->cnt;
            }
        }
    }
}

int query(const char* s) {
    Node* p = root;
    for (int i = 0; s[i]; ++i) {
        int c = s[i] - 'a';
        if (!p->nxt[c]) return 0;
        p = p->nxt[c];
    }
    return p->cnt;
}

void destroy(Node* p) {
    for (int i = 0; i < 26; ++i)
        if (p->nxt[i]) destroy(p->nxt[i]);
    delete p;
}

int main() {
    int P;
    while (scanf("%d", &P) == 1) {
        root = new Node();
        char str[25];
        for (int i = 0; i < P; ++i) {
            scanf("%s", str);
            insert(str, i);
        }
        int Q; scanf("%d", &Q);
        while (Q--) {
            scanf("%s", str);
            printf("%d\n", query(str));
        }
        destroy(root);
    }
    return 0;
}

複雜度

• 構建：每商品名長度 L，插入所有後綴 O(L²)，總長度和 ≤ 200,000，L ≤ 20，極快。
• 查詢：O(|query|)。
• 記憶體：節點數 ≤ 總後綴長度 ≈ 200,000 × 20 / 2 = 2,000,000，符合限制。