欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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;
}

 

相关标签: trie