trie

在一个字符串集合当中进行字符串的插入和查找，采用的是由上而下的存储从首字母开始的一个树结构。

进行字符串的插入操作：

int insert(char str[])
{
    int p = 0;
    for(int i = 0;str[i];i++)
    {
        int u = str[i] - ‘a‘;
        if(!s[p][u]) s[p][u] = ++idx;
        p = s[p][u];
    }
    return cnt[p]++;
}

我们可以用三个字符串来举例：

1. abcd

2. afce

3. abc

可以这么理解：p代表的是这棵trie数的层数（不一定是层数，当不同延展开来的时候是不同字符串字母散开来的序号编号），从上初始化开始的时候是第0层，每增加一个字符串的一个字母的时候，编号p就+1，p的值最后代表的就是字符串往下延伸了几层（也可能是平行延展，当不同字符串出现时）。真正有意义有值的字符串开始是从1开始的，这棵trie树的root结点是默认为0的位置）那么s[p][u]二维数组的第二维就是代表在这一层上有多少个字符串是以这个字母出发继续延展下去的。s[p][u]代表的是第p层的字母以字母u为分支散开去的序号，因为idx是从0开始，终结的是买个字符串结尾处，即标记每个字符串的位置。

1. abcd这个字符串插入的过程如下：

1）p = 0, u = 0, s[0][0]不存在，那么s[0][0] = ++idx = 1, p = s[0][0] = 1;(s[0][0]指的是以根节点root往下延伸开枝散叶以u为叶子得到的) ‘a‘

2）u = 1, s[1][1] = 2 = p;   ‘b‘

3) u = 2, s[2][2] = 3 = p; 

4) u = 3, s[3][3] = 4 = p, cnt[4] = 1;   ‘c‘

2. afce插入过程：

1）u = 0, s[0][0]前面得到过 = 1， p = 1.

2) u = 5, s[1][5] = 5, p = 5;  ‘f‘

3) u = 2, s[5][2] = 6, p = 6, ‘c‘

4) u = 4, s[6][4] = 7, p = 7, cnt[7] = 1;  ‘e‘;

3. abc的插入过程：

1） u = 0, p = 0, s[0][0] = 1,

2) u = 1, s[1][1] = 2,

3) u = 2, s[2][2] = 3, cnt[3] = 1;

综上也就是在字符串集合当中有{abcd, afce, abc}; 分别代表的是cnt[4], cnt[7], cnt[3]各为1。

查找的时候类似，有的话就赋值，然后以新的起点这里继续往下寻找，for循环完查找结束之后，返回cnt[p]即是字符串的个数。

查找的代码如下：

int search(char str[])
　　int p = 0;
　　for(int i = 0;str[i];i++)
　　{int u = str[i] - ‘a‘;
    if(!s[p][u]) return 0;
    p = s[p][u];    
}
    return cnt[p];

其实只要把s[p][u]理解成序号为p的字母往下延伸的某个字母u的编号即可以了，然后再将p指针不断的指向下面这个新位置。最后字符串插入或者循环结束，用上面只要出现过就加一次的cnt数组来计算字符串的出现次数。

完整的代码：

#include <cstdio>
#include <iostream>
using namespace std;
const int N = 100010;
int s[N][26], cnt[N], idx;
int insert(char str[])
{
    int p = 0;
    for(int i = 0;str[i];i++)
    {
        int u = str[i] - ‘a‘;
        if(!s[p][u]) s[p][u] = ++idx;
        p = s[p][u];
    }
    return cnt[p]++;
}
int search(char str[])
{
    int p = 0;
    for(int i =0;str[i];i++)
    {
        int u = str[i] - ‘a‘;
        if(!s[p][u]) return 0;
        p = s[p][u];
    }
    return cnt[p];
}
int main()
{
    int n;
    cin>>n;
    char a,b[101];
    while(n--){
    cin>>a;
    if(a == ‘I‘)
    {
        cin>>b;
        insert(b);
    }
    else if (a == ‘Q‘)
    {
        cin>>b;
        cout<<search(b)<<endl;
    }
    }
}

trie

原文：https://www.cnblogs.com/longxue1991/p/12686205.html