Trie树 hihocoder 1014

字典树的基本应用
#include<queue>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define ll long long

#define inf 1000000000

#define mod 1000000007

using namespace std;

int read()

{

    int x=0,f=1;

    char ch=getchar();

    while(ch<'0'||ch>'9')

    {

        if(ch=='-')f=-1;

        ch=getchar();

    }

    while(ch>='0'&&ch<='9')

    {

        x=x*10+ch-'0';

        ch=getchar();

    }

    return x*f;

}

const int sigma=26;

typedef struct node

{

    int id;

    struct node *next[sigma];

}Trie;

const int N=100000+10;

void insert(Trie *root,char *str)

{

    Trie *p=root;

    int n=strlen(str);

    for(int i=0;i<n;i++)

    {

        int c=str[i]-'a';

        if(p->next[c]==NULL)

        {

            Trie *tmp=new Trie;

            for(int j=0;j<sigma;j++) tmp->next[j]=NULL;

            tmp->id=0;

            p->next[c]=tmp;

        }

        p->id++;

        p=p->next[c];

    }

    p->id++;

}

int search(Trie *root,char *str)

{

    Trie *p=root;

    int n=strlen(str);

    for(int i=0;i<n;i++)

    {

        int c=str[i]-'a';

        if(p->next[c]==NULL) return 0;

        p=p->next[c];

    }

    return p->id;

}

void Del(Trie *root)

{

    for(int i=0;i<sigma;i++) if(root->next[i]!=NULL) Del(root->next[i]);

    delete root;

}

char str[N];

int main()

{

    int cnt=0;

    Trie *root=new Trie;

    for(int i=0;i<sigma;i++) root->next[i]=NULL;

    root->id=false;

    int n;

    n=read();

    for(int i=1;i<=n;i++)

    {

        scanf("%s",str);

        insert(root,str);

    }

    int m=read(),idx;

    while(m--)

    {

        scanf("%s",str);

        idx=search(root,str);

        printf("%d\n",idx);

    }

    Del(root);

    return 0;

}
巴特西

Trie树 hihocoder 1014

Trie树 hihocoder 1014

最新文章

热门文章
