P3879 [TJOI2010]阅读理解

对于 trie 树上的每一个节点，开一个 set ，记录哪些短文出现了该单词。

查看代码

#include <iostream>
#include <cstdio>
#include <string>
#include <set>
using std::cin;
using std::set;
using std::string;
const int N = 5e5 + 10;
int n, m;
int idx, tr[N][26];
set<int> v[N];
void insert(string str, int id)
{
    int p = 0;
    for (int i = 0; i < str.size(); i++)
    {
        int t = str[i] - 'a';
        if (!tr[p][t])
            tr[p][t] = ++idx;
        p = tr[p][t];
    }
    v[p].insert(id);
}
void query(string str)
{
    int p = 0;
    for (int i = 0; i < str.size(); i++)
    {
        int t = str[i] - 'a';
        if (!tr[p][t])
            return;
        p = tr[p][t];
    }
    for (auto i : v[p])
        printf("%d ", i);
}
int main()
{
    scanf("%d", &n);
    for (int i = 1, a; i <= n; i++)
    {
        scanf("%d", &a);
        while (a--)
        {
            string str;
            cin >> str;
            insert(str, i);
        }
    }
    scanf("%d", &m);
    while (m--)
    {
        string str;
        cin >> str;
        query(str);
        puts("");
    }
    return 0;
}