AcWing 000. 字典树-模板
原题链接
中等
作者:
CqAq
,
2024-04-03 21:25:18
,
所有人可见
,
阅读 4
算法1
C++ 代码
#include <bits/stdc++.h>
using namespace std;
///字典树查询字符串是否完整出现过
const int N = 2e6 + 5;
int n, m, nex[N][28];//以第i个结点起,到j这个字母结束的下一个地址
int idx = 2, cnt[N];
void insert(char ch[]){
//int len = strlen(ch + 1);如果从1输入的话
int len = strlen(ch);
int x = 1;
for(int i = 0; i < len; ++ i){
if(!nex[x][ch[i] - 'a']) nex[x][ch[i] - 'a'] = idx ++;//如果没有以第i个结点起,到j这个字母结束的下一个地址,那么就新建一个点
x = nex[x][ch[i] - 'a'];/// 移动到下一个点
cnt[x] ++;
}
}
bool check(char ch[]){
int len = strlen(ch);
int x = 1;
for(int i = 0; i < len; ++ i) x = nex[x][ch[i] - 'a'];
return cnt[x];
}
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; ++ i){
//直接将字符串插入到字典树中
char ch[N]; cin >> ch;
insert(ch);
}
while(m --){
char ch[N]; cin >> ch;
cout << (check(ch) ? "Y\n" : "N\n");
}
return 0;
}