Repository HDU - 2846 (字典树)
程序员文章站
2022-04-17 21:31:23
...
题意:给出一组单词,再给出一组字符串,问这组字符串在这组单词出现过多少次?
题解:使用字典树,对于每个单词,从每一个位置开始都放入字典树中,但是有一点要注意,如果字符串是abab,这样如果统计ab那么岂不是多算了一个么,所以使用一个数组统计当前到了哪个单词(具体可见代码),最后跟据字典树查找即可。
附上代码:
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxnode=1e6+50;
const int sigma_size=26;
const int maxn=35;
struct Trie{
int ch[maxnode][sigma_size];
int val[maxnode];
int id[maxnode];
int sz;
void clear(){
sz=1;
memset(ch[0],0,sizeof(ch[0]));
memset(val,0,sizeof(val));
memset(id,0,sizeof(id));
}
int idx(char c){
return c-'a';
}
void insert(char *s,int v){
int u=0,n=strlen(s);
for(int i=0;i<n;i++){
int c=idx(s[i]);
if(!ch[u][c]){
memset(ch[sz],0,sizeof(ch[sz]));
ch[u][c]=sz++;
}
u=ch[u][c];
if(id[u]!=v){
val[u]++;
}
id[u]=v;
}
}
int find_prefixes(char *s,int len){
int u=0,ans=0;
for(int i=0;i<len;i++){
if(s[i]=='\0'){
return 0;
}
int c=idx(s[i]);
if(!ch[u][c]){
return 0;
}
u=ch[u][c];
}
return val[u];
}
};
Trie trie;
int main()
{
char s[maxn];
int p,q;
scanf("%d",&p);
trie.clear();
for(int i=1;i<=p;i++){
scanf("%s",s);
int len=strlen(s);
for(int j=0;j<len;j++){
trie.insert(s+j,i);
}
}
scanf("%d",&q);
for(int i=0;i<q;i++){
scanf("%s",s);
printf("%d\n",trie.find_prefixes(s,strlen(s)));
}
return 0;
}
上一篇: 锁持有者管理器AbstractOwnableSynchronizer
下一篇: 老油条的教导