字典树练习

[TJOI2010] 阅读理解

英语老师留了 $N$ 篇阅读理解作业，但是每篇英文短文都有很多生词需要查字典，为了节约时间，现在要做个统计，算一算某些生词都在哪几篇短文中出现过。

第一行为整数 $N$ ，表示短文篇数，其中每篇短文只含空格和小写字母。

按下来的 $N$ 行，每行描述一篇短文。每行的开头是一个整数 $L$ ，表示这篇短文由 $L$ 个单词组成。接下来是 $L$ 个单词，单词之间用一个空格分隔。

然后为一个整数 $M$ ，表示要做几次询问。后面有 $M$ 行，每行表示一个要统计的生词。

对于每个生词输出一行，统计其在哪几篇短文中出现过，并按从小到大输出短文的序号，序号不应有重复，序号之间用一个空格隔开（注意第一个序号的前面和最后一个序号的后面不应有空格）。如果该单词一直没出现过，则输出一个空行。

思路

由于 $1\le M \le 10^4$ ，$1\le N\le 10^3$ 且每篇短文长度小于等于 $5\times 10^3$ ，所以考虑直接建 $1000$ 个字典树，每个开 $5000$ 个结点。

然后就是普通的字典树的插入和查询操作。

注意节点标号不能定义成全局的，而是每个字典树都有一个，否则会 MLE 和 WA 。因为这东西查了半天….

代码

#include<bits/stdc++.h>
#define N 1010
#define M 5010
#define L 25

using namespace std;

int n,m;
char s[L];

struct Trie{
    int tot;
    struct node{
        int son[26];
        bool vh;
    }nod[M];
    void Insert(char *s) {
        int now=0;
        for(int i=0;s[i];i++) {
            int ch=s[i]-'a';
            if(!nod[now].son[ch]) nod[now].son[ch]=++tot;
            now=nod[now].son[ch];
        }
        nod[now].vh=true;
    }
    bool Check(char *s) {
        int now=0;
        for(int i=0;s[i];i++) {
            int ch=s[i]-'a';
            if(!nod[now].son[ch]) return false;
            now=nod[now].son[ch];
        }
        if(!nod[now].vh) return false;
        return true;
    }
}TRIE[N];

void solve() { 
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        int l;
        scanf("%d",&l);
        for(int j=1;j<=l;j++) {
            scanf("%s",s);
            TRIE[i].Insert(s);
        }
    }
    scanf("%d",&m);
    for(int i=1;i<=m;i++) {
        scanf("%s",s);
        for(int j=1;j<=n;j++) if(TRIE[j].Check(s)) printf("%d ",j);
        printf("\n");
    }
}

int main() {
    solve();
    return 0;
}