Trie Tree

    技术2022-05-13  20

    #include<iostream>#include<cstring>#define N 300 //有N个单词#define M 1000000//有M次查询#define kind 26//26个英文字母using namespace std;struct Treenode{    int count;    Treenode *next[kind];    Treenode(){        for(int i=0; i<kind; i++)            next[i]=NULL;        count=1;    }};void insert(Treenode *&root, char *word){    int i=0,j,l=strlen(word),branch;    Treenode *location=root;    if(location==NULL){        location=new Treenode();        root=location;    }

        for(i=0; i<l; i++){        branch=word[i]-'a';        if(location->next[branch])            location->next[branch]->count++;        else            location->next[branch]=new Treenode();        location=location->next[branch];    }}int search(Treenode *&root, char *word){    int i, ans=0, l=strlen(word),branch;    Treenode *location=root;    if(location==NULL) return 0;    for(i=0; i<l; i++){        branch=word[i]-'a';        if(!location->next[branch])            return 0;

            location=location->next[branch];        ans=location->count;    }    return ans;}

    int main(){    int i,j,n,m;    char word[50];    Treenode *root=NULL;    scanf("%d", &n);    for(i=0; i<n; i++){        scanf("%s",word);        insert(root, word);    }    scanf("%d",&m);    for(i=0; i<m; i++){        scanf("%s",word);        printf("%d/n",search(root, word));    }

        return 0;}


    最新回复(0)