算法解析

本题使用的是利用数组来模拟树。定义数组trie[N][26]。把它理解成有N个块排成一排，每个块中有26个小格子。一块就意味着树结构中的节点，而26个小格子表示本节点的值是a-z中的哪一个，那么trie[N][26]存储的值就是指向下一个节点的数组下标。如图所示：

解释清了trie结构，那么来看本题算法。本题算法主要是插入insert操作和查询query操作。加入了一个count[N]数组，用作计数。count[2] = 1表示单词到第2块(从0算起)结尾的单词数量是1个。根据上图可知:count[0] = 0, count[1] = 0, count[2] = 1, count[3] = 1.

insert代码如下：

int trie[N][26],count[N], idx = 0;

void insert(string str){
    int p = 0;
    for(int i = 0; str[i]; i++){
        int u = str[i] - 'a'; // 用于确定26个格子的哪一个
        if(trie[p][u] == 0) trie[p][u] = ++idx;
        p = trie[p][u];
    }
    count[p] ++;
}

idx是全局变量，用于判断当前处于哪一个块。而p是局部变量，只是用来记录单词内部的指针。

query代码如下：

void insert(string str){
    int p = 0;
    for(int i = 0; str[i]; i++){
        int u = str[i] - 'a';
        if(trie[p][u] == 0) return 0;
        p = trie[p][u];
    }
    return count[p];
}

逻辑和插入是一样的。