题目提示已经很清楚了~
贴代码……
#include <iostream>
#include <cstdio>
#include <cstring> using namespace std;
const int MAXN = + ;
const int alNum = ;
struct Node{
int cnt;
int next[alNum];
void init(){
memset(next,-,sizeof(next));
cnt = ;
return;
}
};
Node trie[MAXN];
int tt;
void build_trie(char str[]){
int len = strlen(str);
int p = ;
for(int i = ;i < len;i++){
int ch = str[i] - 'a';
if(trie[p].next[ch] == -){
trie[tt].init();
trie[p].next[ch] = tt++;
}
p = trie[p].next[ch];
trie[p].cnt++;
}
}
int quercy(char str[]){
int len = strlen(str);
int p = ;
for(int i = ;i < len;i++){
int ch = str[i] - 'a';
if(trie[p].next[ch] == -){
return ;
}
p = trie[p].next[ch];
}
return trie[p].cnt;
}
int main(){
// freopen("input.txt","r",stdin);
int n,m;
while(~scanf("%d",&n)){
char str[];
tt = ;
trie[tt++].init();
for(int i = ;i < n;i++){
scanf("%s",str);
build_trie(str);
}
scanf("%d",&m);
for(int i = ;i < m;i++){
scanf("%s",str);
int q = quercy(str);
printf("%d\n",q);
}
}
return ;
}
字典树 水题
判断一个是否为另一个的前缀。
注意 9113
911 的情况……
#include <iostream>
#include <cstdio>
#include <cstring> using namespace std;
const int MAXN = + ;
const int NextNum = ; int tt;
struct Node{
int next[NextNum];
bool flag;
void init(){
memset(next,-,sizeof(next));
flag = ;
}
};
Node trie[MAXN];
bool build_trie(char str[]){
int p = ;
int len = strlen(str);
for(int i = ;i < len;i++){
int x = str[i] - '';
if(trie[p].next[x] == -){
trie[tt].init();
trie[p].next[x] = tt++;
}
p = trie[p].next[x];
if(trie[p].flag){
return ;
}
}
for(int i = ;i < NextNum;i++){
if(trie[p].next[i] != -){
return ;
}
}
trie[p].flag = ;
return ;
} int main(){
// freopen("input.txt","r",stdin);
int t;
scanf("%d",&t);
while(t--){
int n;
scanf("%d",&n);
tt = ;
trie[tt++].init();
bool ok = ;
char str[+];
for(int i = ;i < n;i++){
scanf("%s",str);
if(!ok){
continue;
}
ok = build_trie(str);
}
printf("%s\n",ok?"YES":"NO");
}
return ;
}