Trie树

曾经终败给现在 2022-12-31 02:25 189阅读 0赞

# Trie树 201227 #

> 思路 题目 答案

## 题目： ##

输入的第一行为一个正整数n，表示词典的大小，其后n行，每一行一个单词（不保证是英文单词，也有可能是火星文单词哦），单词由不超过10个的小写英文字母组成，可能存在相同的单词，此时应将其视作不同的单词。接下来的一行为一个正整数m，表示小Hi询问的次数，其后m行，每一行一个字符串，该字符串由不超过10个的小写英文字母组成，表示小Hi的一个询问。

## 输出： ##

对于小Hi的每一个询问，输出一个整数Ans,表示词典中以小Hi给出的字符串为前缀的单词的个数。

## 样例输入： ##

5
    babaab
    babbbaaaa
    abba
    aaaaabaa
    babaababb
    5
    babb
    baabaaa
    bab
    bb
    bbabbaab

## 样例输出： ##

1
    0
    3
    0
    0

## 解题代码： ##

#include<cstdio>
    #include<cstring>
    
    using namespace std;
    const int MAX_NODE = 1000000 + 10;
    const int CHARSET = 26; //26个字母
    int trie[MAX_NODE][CHARSET] = {
        0};  //
    int SumOfPassedTheNode[MAX_NODE] = {
        0}; //经过SumOfPassedTheNode[x]这个x结点的单词数量
    int k = 1;
    
    void insert(char *word) {
        
        int len = strlen(word);
        int nodePosition = 0;
        for (int i = 0; i < len; i++) {
        
            int c = word[i] - 'a';
            if (!trie[nodePosition][c]) {
            //如果这个结点下这个字符被存过没有，没有被存过就存下来
                trie[nodePosition][c] = k; //然后通过这种方式表示下个结点是啥
                k++;
            }
    //        SumOfPassedTheNode[nodePosition]++; //表示经过本结点的单词有多少个
    //        printf("%c %d  ",word[i],SumOfPassedTheNode[nodePosition]); 
            nodePosition = trie[nodePosition][c]; //表示下个结点在哪
            SumOfPassedTheNode[nodePosition]++; //表示经过本结点的单词有多少个
            //printf("%c %d  ",word[i],SumOfPassedTheNode[nodePosition]); 
    
        }
        //printf("\n");   
        //SumOfPassedTheNode[nodePosition] = 1;  //1 表示这个结点处已经是结尾了
    }
    
    int search(char *word) {
        
        int len = strlen(word);
        int nodePosition = 0;
        int ret=0;
        for (int i = 0; i < len; i++) {
        
            int c = word[i] - 'a';
            if (!trie[nodePosition][c]) {
           //这个结点的这个字符没有被插入过
                return 0;       //则直接返回单词搜索失败
            }
            //ret=SumOfPassedTheNode[nodePosition];
            //printf("%c %d  ",word[i],SumOfPassedTheNode[nodePosition]); 
            nodePosition = trie[nodePosition][c];     //否则，使得访问的位置去到下个结点
        }
        //printf("\n");   
        return SumOfPassedTheNode[nodePosition];  //判断单词尾字符所在的结点是否是尾节点
    }
    
    int main() {
        
        int insertWordSum, searchWordSum;
        char word[20];
        scanf("%d", &insertWordSum);
        while (insertWordSum--) {
        
            scanf("%s", word);
            insert(word);
        }
        //getchar();
        scanf("%d", &searchWordSum);
        while (searchWordSum--) {
        
            scanf("%s", word);
            printf("%d\n", search(word));
        }
        return 0;
    }