题解 | 【模板】Trie 字典树
【模板】Trie 字典树
https://www.nowcoder.com/practice/feed1cd7546a4901965751b9fbf5f8a1
字典树算法讲解可以看其他题解 这里给出一版比较简单的代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
const int N=1e6+1;
char s[N];
int ch[N][70],cnt[N],idx;
void insert(string s){
int p=0;
for(int i=0;s[i];i++){
int j;
j=s[i]-'A';
if(!ch[p][j]){
ch[p][j]=++idx;
}
p=ch[p][j];
cnt[p]++;
}
//cnt[p]++;
}
int query(string s){
int p=0;
for(int i=0;s[i];i++){
int j=s[i]-'A';
if(!ch[p][j]) return 0;
p=ch[p][j];
}
return cnt[p];
}
int main(){
cin.tie(0)->sync_with_stdio(0);
int n,q;
cin >> n >> q;
for(int i=0;i<n;i++){
string s;
cin >> s;
insert(s);
}
for(int i=0;i<q;i++){
string x;
cin >> x;
cout << query(x) << '\n';
}
}
OPPO公司福利 1225人发布