P3879 [TJOI2010] 阅读理解- 字典树

题面

分析

将所有单词存入字典树，重点值怎么判断在哪一行出现过，对于字典树查询的判断字符串是否存在的数组可以开成二维，也就是在查询到某个字符串存在后，再通过循环判断每一层是否存在。

代码

#include <bits/stdc++.h>#define int long longusing namespace std;const int N = 5e5 + 10;int son[N][30];
bitset<1010> vis[N];
int idx;
int n;void insert(string s, int i) {int p = 0;for(int i = 0; i < s.size(); i ++) {int c = s[i] - 'a';if(!son[p][c]) son[p][c] = ++ idx;p = son[p][c];}vis[p][i] = 1;
}vector<int> query(string s) {int p = 0;vector<int> ans;for(int i = 0; i < s.size(); i ++) {int c = s[i] - 'a';if(!son[p][c]) return ans;p = son[p][c];}for(int i = 1; i <= n; i ++) {if(vis[p][i]) ans.push_back(i);}return ans;
}signed main() {ios::sync_with_stdio(false);cin.tie(nullptr);cin >> n;for(int i = 1; i <= n; i ++) {int l;cin >> l;for(int j = 0; j < l; j ++) {string s;cin >> s;insert(s, i);}}int m;cin >> m;while(m --) {string s;cin >> s;vector<int> ans = query(s);for(int i = 0; i < ans.size(); i ++) cout << ans[i] << ' ';cout << "\n";}
}