当前位置：网站首页>字典树（Trie）

字典树（Trie）

2022-07-29 16:51:00 【51CTO】

字典树，顾名思义，就是一种对字母等字符串进行处理的一种特殊数据结构。说白了，就是二十六叉树。定义一个头指针，每次从头指针开始操作。

有两种常用的操作：

1.查询某个字符串的出现次数。

每个节点的count置为0，直到这个字符串结束，在末尾处count++.这样，就记录了该字符串的出现次数。

2.查询某个字符串特定序列出现的次数。

每个节点的count初始化为0，当读入一个字符，则count++。这样，查询时，这个节点count记录的就是从头结点到该结点特定序列出现的次数。可以用于统计单词的前缀一类的题目。

例题：

给你一堆英文单词（可能有4000000个。用普通查询铁定让你TLE）。找出出现次数最多的，输出这个单词，并输出出现的次数。

思路：

懒的写了，参考学长代码

代码如下：

       
       #include <bits/stdc++.h>
       
       using 
       
       namespace 
       
       std;
       
       const 
       
       int 
       
       N
       
       =
       
       2
       
       *
       
       1e5
       
       +
       
       10;
       
       int 
       
       n,
       
       m,
       
       q,
       
       k,
       
       ans,
       
       sum,
       
       top;
       
       char 
       
       ch1[
       
       N],
       
       ch2[
       
       N];
       
       struct 
       
       Dictree
       
       ///字典树
       
{
       
       int 
       
       count;
       
       ///单词出现次数
       
       struct 
       
       Dictree  
       
       *
       
       tree[
       
       26];
       
       ///26个子节点
       
}
       
       *
       
       a;
       
       void 
       
       init()
       
{
       
       a
       
       =
       
       new 
       
       Dictree;
       
       for(
       
       int 
       
       i
       
       =
       
       0; 
       
       i
       
       <
       
       26; 
       
       ++
       
       i)  
       
       ///子节点置空
       
    {
       
       a
       
       ->
       
       tree[
       
       i]
       
       =
       
       NULL;
       
    }
       
}
       
       int 
       
       insert(
       
       char 
       
       str[])
       
{
       
       int 
       
       len,
       
       j;
       
       Dictree 
       
       *
       
       head
       
       =
       
       a;
       
       ///head是头指针
       
       len
       
       =
       
       strlen(
       
       str);
       
       for(
       
       int 
       
       i
       
       =
       
       0; 
       
       i
       
       <
       
       len; 
       
       ++
       
       i)
       
    {
       
       j
       
       =(
       
       int)(
       
       str[
       
       i]
       
       -
       
       'a');
       
       if(
       
       head
       
       ->
       
       tree[
       
       j]
       
       ==
       
       NULL)
       
        {
       
       head
       
       ->
       
       tree[
       
       j]
       
       =
       
       new 
       
       Dictree;
       
       head
       
       =
       
       head
       
       ->
       
       tree[
       
       j];
       
       head
       
       ->
       
       count
       
       =
       
       0;
       
       for(
       
       int 
       
       k
       
       =
       
       0; 
       
       k
       
       <
       
       26; 
       
       k
       
       ++)
       
            {
       
       head
       
       ->
       
       tree[
       
       k]
       
       =
       
       NULL;
       
            }
       
        }
       
       else 
       
       head
       
       =
       
       head
       
       ->
       
       tree[
       
       j];
       
    }
       
       head
       
       ->
       
       count
       
       ++;
       
       return 
       
       head
       
       ->
       
       count;
       
}
       
       int 
       
       main()
       
{
       
       int 
       
       num,
       
       maxx
       
       =
       
       0;
       
       init();
       
       scanf(
       
       "%d",
       
       &
       
       num);
       
       for(
       
       int 
       
       i
       
       =
       
       0; 
       
       i
       
       <
       
       num; 
       
       ++
       
       i)
       
    {
       
       scanf(
       
       "%s",
       
       ch1);
       
       int 
       
       ans
       
       =
       
       insert(
       
       ch1);
       
       if(
       
       ans
       
       >
       
       maxx)
       
        {
       
       maxx
       
       =
       
       ans;
       
       strcpy(
       
       ch2,
       
       ch1);
       
        }
       
    }
       
       printf(
       
       "%s %d\n", 
       
       ch2,
       
       maxx);
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.

数据范围较小，可用map映射

       
       #include <bits/stdc++.h>
       
       using 
       
       namespace 
       
       std;
       
       const 
       
       int 
       
       N
       
       =
       
       2
       
       *
       
       1e5
       
       +
       
       10;
       
       int 
       
       n,
       
       m,
       
       q,
       
       k,
       
       ans,
       
       sum,
       
       top;
       
       char 
       
       ch1[
       
       N],
       
       ch2[
       
       N];
       
       map
       
       <
       
       string,
       
       int
       
       >
       
       dictree;
       
       int 
       
       main()
       
{
       
       scanf(
       
       "%d",
       
       &
       
       n);
       
       for(
       
       int 
       
       i
       
       =
       
       0; 
       
       i
       
       <
       
       n; 
       
       i
       
       ++)
       
    {
       
       scanf(
       
       "%s",
       
       ch1);
       
       dictree[
       
       ch1]
       
       ++;
       
       ///每个单词出现次数
       
    }
       
       map
       
       <
       
       string,
       
       int 
       
       >::
       
       iterator 
       
       ita,
       
       itb;
       
       for(
       
       ita
       
       =
       
       dictree.
       
       begin(),
       
       itb
       
       =
       
       dictree.
       
       begin(); 
       
       ita
       
       !=
       
       dictree.
       
       end(); 
       
       ++
       
       ita)
       
    {
       
       if(
       
       ita
       
       ->
       
       second
       
       >
       
       itb
       
       ->
       
       second)
       
        {
       
       itb
       
       =
       
       ita;
       
        }
       
    }
       
       cout
       
       <<
       
       itb
       
       ->
       
       first
       
       <<
       
       " "
       
       <<
       
       itb
       
       ->
       
       second
       
       <<
       
       endl;
       
       return 
       
       0;
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.

原网站

版权声明
本文为[51CTO]所创，转载请带上原文链接，感谢
https://blog.51cto.com/u_15368396/5526883

当前位置：网站首页>字典树（Trie）

字典树（Trie）

边栏推荐

猜你喜欢

随机推荐