正題

luogu 3879
ybtoj Trie-4

---

題目大意

給你n篇文章，還有m個單詞，問你這些單詞在哪幾篇文章中出現過

---

解題思路

對文章中的單詞建Trie，然后那查詢的單詞去匹配

---

代碼

#include<map> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define N 500100 #define mp(x,y) make_pair(x,y) using namespace std; int n, m, w; char s[N]; map<pair<int, int>, int>to;//直接存會MLE，用map，以時間換空間 vector<int> a[N]; void insert(char* s, int v)//存單詞 {int now = 0, y, n = strlen(s+1);for (int i = 1; i <= n; ++i){y = s[i] - 'a';if (!to[mp(now, y)]) to[mp(now, y)] = ++w;now = to[mp(now, y)];}if (!a[now].size()) a[now].push_back(v);else if (a[now][a[now].size() - 1] != v) a[now].push_back(v);//不重復存 } void ask(char* s) {int now = 0, y, n = strlen(s+1), p = 0;for (int i = 1; i <= n; ++i){y = s[i] - 'a';if (!to[mp(now, y)]){p = 1;break;}else now = to[mp(now, y)];}if (p || !a[now].size()) puts(" ");else{printf("%d", a[now][0]);for (int i = 1; i < a[now].size(); ++i)printf(" %d", a[now][i]);putchar(10);}return; } int main() {scanf("%d", &n);for (int i = 1; i <= n; ++i){scanf("%d", &m);while(m--){scanf("%s", s+1);insert(s, i);}}scanf("%d", &n);while(n--){scanf("%s", s+1);ask(s);}return 0; }

總結

以上是生活随笔為你收集整理的【Trie】阅读理解（luogu 3879/ybtoj Trie-4）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。