AcWing_835_Trie字符串统计

题目

代码详解

字典树也叫Trie树、前缀树，针对字符串进行维护的数据结构。
概念

$$ \begin{align} & 字典树，顾名思义，是关于“字典”的一棵树。即：它是对于字典的一种存储方式\\ & 这个词典中的每个“单词”就是从根节点出发一直到某一个目标节点的路径，\\ & 路径中每条边的字母连起来就是一个单词 \end{align} $$

$思路：用数组模拟链表，效率高$

$依次插入$

  a    
  abc 
  bac  
  bbc 
  ca

$效果$

举例

$依次插入$

  abc 
  bcd 
  abd 
  ab

效果

$以代码对应数组son[p][u]详细分析$

$\color{red}{插入abc}$

$p\space =\space 0$
$a：son[0][0]\space 为\space 0$
$son[0][0] \space =\space idx \space =\space 1$
$p\space =\space 1$
$b：son[1][1]\space 为 0$
$son[1][1]\space =\space idx \space =\space 2$
$p\space =\space 2$
$c：son[2][2]\space 为\space 0$
$son[2][2]\space = \space idx \space =\space 3$
$p = 3 \space\space cnt[3] 为 1 \space\space 结束$

此时的运行结果

 cnt[N]： 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0  
 son[N][26]
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

$\color{red}{插入bcd}$

$p\space =\space 0$
$b：son[0][1]\space 为\space 0$
$son[0][0] \space =\space idx \space =\space 4$
$p\space =\space 4$
$c：son[4][2]\space 为 0$
$son[4][2]\space =\space idx \space =\space 5$
$p\space =\space 5$
$d：son[5][3]\space 为\space 0$
$son[5][3]\space = \space idx \space =\space 6$
$p = 6 \space\space cnt[6] 为 1 \space\space 结束$

此时的运行结果

cnt[N]： 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0   
son[N][26]
1 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

$\color{red}{插入abd}$

$p\space =\space 0$
$a：son[0][0]\space 为\space 1$
$p\space =\space 1$
$b：son[1][1]\space 为 2$
$p\space =\space 2$
$d：son[2][3]\space 为\space 0$
$son[2][3]\space = \space idx \space =\space 7$
$p = 7 \space\space cnt[7] 为 1 \space\space 结束$

此时的运行结果

cnt[N]： 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0  
son[N][26]
1 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 3 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

$\color{red}{插入ab}$

$p\space =\space 0$
$a：son[0][0]\space 为\space 1$
$p\space =\space 1$
$b：son[1][1]\space 为 2$
$p = 2 \space\space cnt[2] 为 1 \space\space 结束$

此时的运行结果

cnt[N]： 0 0 1 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
son[N][26]
1 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 3 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

心得

$$ \begin{align} & idx 辅助构建前后节点的链式关系\\ & son[N][26] 数组：\\ & 第一维是当前节点所在行数\\ & 第二维是当前节点携带的哪个字母\\ & 其值作为指针表示下一个节点所在行数 \end{align} $$

一些常识

$$ \begin{align} & idx作为全局变量存放在静态数据区，该区的内存值在程序初始阶段\\ & 会被设置为0，所以存放在该区的值默认情况下都是被初始化为0\\ & （静态数据区中的变量只允许初始化一次，即程序开始阶段的初始化） \end{align} $$

$$ \begin{align} & 有些时候程序会出现莫名其妙的错误，可能是储存在栈区的局部变量，\\ &该区并不会在程序初始阶段初始为0。我们在每次调用函数的时候会在栈区\\ &顶部推入新的栈帧，但是函数调用完成并回到调用点的时候，编译器只是\\ &把指向栈帧顶部的指针指回上一个栈帧的顶部，这个过程中并没有重新将\\ &被弹出的栈帧的内存的值改为0。所以如果下次又有新的栈帧被分配到该内\\ &存上并且没有初始化变量的值，那么就很可能会使用到上一次栈帧中\\ &遗留下来的内存值，也就是垃圾值。 \end{align} $$

完整代码

#include<iostream>
using namespace std;

const int N = 1e5 + 10;

int son[N][26], cnt[N], idx;
char str[N];

void insert(char *str)
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
    }
    cnt[p] ++ ;
}

int query(char* str)
{
    int p = 0;
    for (int i = 0; str[i]; i ++) 
    {
        int u = str[i] - 'a';
        if (!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}

int main()
{
    int n;
    scanf("%d", &n);
    while (n -- )
    {
        char op[2];     //读两个 
        scanf("%s%s", op, str);
        if (*op == 'I')  insert(str);
        else    printf("%d\n", query(str));
        
    }
    
    // 打印 son[N][26]
    for (int i = 0; i < 10; i ++ ) {
        for (int j = 0; j < 26; j ++ ) {
            cout << son[i][j] << " ";
        }
        cout << endl;
    }
    
    return 0;
}