（每日一练C++）CC210 词频统计

怼烎@ 2023-10-04 18:07 72阅读 0赞

### 描述 ###

给定一个string数组**article**及其大小**n**及一个待统计单词**word**，请返回该单词在数组中出现的频数。文章的词数在1000以内。

struct Node{
        char data;
        int cnt;
        int ch[2],next;// 0 left child, 1 right child
        Node(){}
        Node(char c):data(c){cnt=ch[0]=ch[1]=next=0;}
    };
    
    struct Trie{
        Node* node;
        int nodecount;
    	
        Trie(){
            node=new Node[500005];
            node[0]=Node('n');
            nodecount=1;
        }
        ~Trie(){
            delete [] node;
        }
        
        int appendnode(char x){
            node[nodecount]=Node(x);
            return nodecount++;
        }
    
        void append(int id,const char* str){
            while(*str){
                if(*str==node[id].data){
                    if(!str[1])node[id].cnt++;
                    if(!node[id].next&&str[1]){
                        node[id].next=appendnode(str[1]);
                    }
                    id=node[id].next;
                    str++;
                }else{
                    int cid=*str<node[id].data?0:1;//0 left child, 1 right child
                    if(!node[id].ch[cid]){
                        node[id].ch[cid]=appendnode(str[0]);
                    }
                    id=node[id].ch[cid];
                }
            }
        }
    
        int find(int id,const char *str){
            while(*str){
                if(*str==node[id].data){
                    if(!str[1])return id;
                    if(!node[id].next){
                        return -1;
                    }
                    id=node[id].next;
                    str++;
                }else{
                    int cid=*str<node[id].data?0:1;//0 left child, 1 right child
                    if(!node[id].ch[cid]){
                        return -1;
                    }
                    id=node[id].ch[cid];
                }
            }
            return -1;
        }
    };
    
    class Frequency {
    public:
        int getFrequency(vector<string> article, int n, string word) {
            Trie trie;
            for(int i=0;i<n;i++){
                trie.append(0,article[i].c_str());
            }
            int id=trie.find(0,word.c_str());
            return trie.node[id].cnt;
        }
    };