（模板）hdoj1251（字典树模板题）

题目链接：https://vjudge.net/problem/HDU-1251

题意：给定一系列字符串之后，再给定一系列前缀，对每个前缀查询以该字符串为前缀的字符串个数。

思路：

　　今天开始学字典树，从入门题开始。用数组实现,count数组表示每个结点出现次数，trie[0]为根节点。插入和查询一个字符串的复杂度为O(len)。len为字符串的长度。

AC code:

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

const int maxn=1e6+;   //树的大小，尽量开大点

int trie[maxn][],num[maxn],cnt;

char str[];

void insert(char *s){

    int len=strlen(s);

    int u=;

    for(int i=;i<len;++i){

        int t=s[i]-'a';

        if(!trie[u][t]){

            ++cnt;

            memset(trie[cnt],,sizeof(trie[cnt]));

            trie[u][t]=cnt;

        }

        u=trie[u][t];

        ++num[u];

    }

}

int query(char *s){

    int len=strlen(s);

    int u=;

    for(int i=;i<len;++i){

        int t=s[i]-'a';

        if(!trie[u][t]) return ;

        u=trie[u][t];

    }

    return num[u];

}

int main(){

    cnt=;

    memset(trie[],,sizeof(trie[]));

    memset(num,,sizeof(num));

    while(gets(str),str[]!='\0')

        insert(str);

    while(~scanf("%s",str))

        printf("%d\n",query(str));

    return ;

}

巴特西

（模板）hdoj1251（字典树模板题）

最新文章

热门文章