红魔咖啡馆

头发越掉越多，头发越掉越少

0%

【字符串】字典树

发表于 更新于 分类于 ，
本文字数： 6k 阅读时长 ≈ 11 分钟
介绍了字典树的原理与使用

字典树(trie)

给予n个单词，在这n个单词中查询给定的单词是否存在

创建一个自动机，使得其只接受指定的单词，我们只需要从起始状态开始，按照给定单词中的字符依次向前转移，创建新状态，并将最终状态设为接受状态即可，若输入字符串不是指定单词，则不能被自动机接受

对于多个单词，只需要回到起始状态，按照新单词中的字符依次构造即可

遍历

使用string遍历每一个单词比较，s1==s2，时间复杂度为\(O(nm)\)，m为单词长度

若询问q次，则复杂度高达\(O(nmq)\)

字典树

字典树是一种树形结构，树的每个节点上存储了一个字符

标红的节点表示存在一个以该节点字符结尾的字符串

可以发现，以某个字符结尾的字符串在trie树上是唯一的，因为该节点只有一个父节点，沿着往上即可获得唯一的字符串。

还可以发现，若按照前序遍历，每个节点的字符是按字典序排列的，故trie树还可以用于排序

建树

建立一个根节点，将字符串每一个字符依次从根节点插入，若存在对应字符节点便沿用，否则在上个父节点基础上新建节点，传入结尾位置时标记（是否结尾或第几个相同单词）

时间复杂度\(O(mn)\)

询问

将读入的字符串从根节点开始一个个字符比对，若某个字符在同层节点中都没有则不存在该字符串，若到达该字符串末尾，但此时节点并未标记结尾位置，也判断为不存在该字符串。否则判断为存在

时间复杂度：\(O(qx)\)，x为每次询问字符串长度，共q次询问

删除

  1. 判断是否有子节点
  2. 若没有子节点，标记不为一时-1，为1时递归删除到根节点

存储

用数组表示层数，每层再用数组表示26个字符在该层出现的次数

缺点：若字符少可行，若字符数过多，或每层分配的节点过多，占用空间会过大

时间换空间：使用map或unordered_map，但时间复杂度会变高

板子

结构体实现

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
#include <bits/stdc++.h>
using namespace std;
const int N = 26;
// 开辟空间
struct trieNode{
  char val;
  trieNode** son;
  int cnt;
  trieNode(char c){
    val = c;
    son = new trieNode*[N];
    for (int i = 0;i<N;i++) son[i]=nullptr;
    cnt = 0;
  }
};
trieNode* root;
// 插入操作
void insert(string s){
  trieNode* p = root;
  for (int i = 0;i<s.size();i++){
    int c = s[i]-'a';
    if (!p->son[c])p->son[c] = new trieNode(c);
    p = p->son[c];
  }
  p->cnt++;
}
// 查询操作
int query(string s){
  trieNode* p = root;
  for (int i = 0;i<s.size();i++){
    int c = s[i]-'a';
    if (!p->son[c]) return 0;
    p = p->son[c];
  }
  return p->cnt;
}
int main(){
  root = new trieNode(' ');
  for (int i = 0;i<5;i++){
    string s;
    cin >> s;
    insert(s);
  }
  for (int i = 0;i<5;i++){
    string s;
    cin >> s;
    cout << query(s)<<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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;
const int N = 26;
const int M = 105;
// 开辟空间
int trie[M][N];
int cnt[M];
int idx = 0;
// 插入操作
void insert(string s){
  int p = 0;
  for (int i = 0;i<s.size();i++){
    int c = s[i]-'a';
    if (!trie[p][c])trie[p][c]=++idx;
    p = trie[p][c];
  }
  cnt[p]++;
}
// 查询操作
int query(string s){
  int p = 0;
  for (int i = 0;i<s.size();i++){
    int c = s[i]-'a';
    if (!trie[p][c]) return 0;
    p = trie[p][c];
  }
  return cnt[p];
}
int main(){
  for (int i = 0;i<5;i++){
    string s;
    cin >> s;
    insert(s);
  }
  for (int i = 0;i<5;i++){
    string s;
    cin >> s;
    cout << query(s)<<endl;
  }
  return 0;
}

map实现

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
#include <bits/stdc++.h>
using namespace std;
const int N = 26;
const int M = 105;
// 开辟空间
vector<map<char,int>> trie; // 或使用unordered_map
int cnt[M];
int idx = 0;
// 插入操作
void insert(string s){
  int p = 0;
  for (int i = 0;i<s.size();i++){
    int c = s[i]-'a';
    if (!trie[p][c])trie[p][c]=++idx;
    p = trie[p][c];
  }
  cnt[p]++;
}
// 查询操作
int query(string s){
  int p = 0;
  for (int i = 0;i<s.size();i++){
    int c = s[i]-'a';
    if (!trie[p][c]) return 0;
    p = trie[p][c];
  }
  return cnt[p];
}
int main(){
  trie = vector<map<char,int>>(M);
  for (int i = 0;i<5;i++){ 
    string s;
    cin >> s;
    insert(s);
  }
  for (int i = 0;i<5;i++){
    string s;
    cin >> s;
    cout << query(s)<<endl;
  }
  return 0;
}

应用-查询前缀

题目描述

给定 \(n\) 个模式串 \(s_1, s_2, \dots, s_n\) 和 \(q\) 次询问，每次询问给定一个文本串 \(t_i\)，请回答 \(s_1 \sim s_n\) 中有多少个字符串 \(s_j\) 满足 \(t_i\) 是 \(s_j\) 的前缀。

一个字符串 \(t\) 是 \(s\) 的前缀当且仅当从 \(s\) 的末尾删去若干个（可以为 0 个）连续的字符后与 \(t\) 相同。

输入的字符串大小敏感。例如，字符串 Fusu 和字符串 fusu 不同。

输入格式

本题单测试点内有多组测试数据。

输入的第一行是一个整数，表示数据组数 \(T\)。

对于每组数据，格式如下：
第一行是两个整数，分别表示模式串的个数 \(n\) 和询问的个数 \(q\)。
接下来 \(n\) 行，每行一个字符串，表示一个模式串。
接下来 \(q\) 行，每行一个字符串，表示一次询问。

输出格式

按照输入的顺序依次输出各测试数据的答案。
对于每次询问，输出一行一个整数表示答案。

数组实现

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> PII;
const int N = 3e6 + 10;
const int M = 70;
const double pi = acos(-1.0);
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const double eps = 1e-6;
int t;
int trie[N][M];
int cnt[N];
int idx = 0;
// char到int的转换
int ascii(char c){
  if (c>='a'&& c<='z') return c-'a'+26;
  else if (c>='A'&&c<='Z') return c-'A';
  else return c-'0'+52;
}
// 插入操作
void insert(string s){
  int p = 0;
  for (int i = 0;i<s.size();i++){
    int c = ascii(s[i]);
    if (!trie[p][c]) trie[p][c]=++idx;
    p=trie[p][c];
    cnt[p]++; // 这里与查询整个单词不同，需要每层计数
  }
}
// 询问操作
int query(string s){
  int p = 0;
  //int sum = 0;
  for (int i = 0;i<s.size();i++){
    int c =ascii(s[i]);
    if (!trie[p][c]) return 0;
    p=trie[p][c];
    // sum+=cnt[p];
  }
  return cnt[p];
}
int main()
{
  ios
  cin >> t;
  while(t--){
    int n , q;
    cin >> n >> q;
    // 每次清空使用过的部分
    for (int i = 0;i<=idx;i++){
      for (int j = 0;j<=M;j++){
        trie[i][j]=0;
      }
    }
    for(int i = 0;i<=idx;i++){
      cnt[i]=0;
    }
    idx = 0;
    for (int i = 0; i<n;i++){
      string s;
      cin >> s;
      insert(s);
    }
    for (int i = 0;i<q;i++){
      string s;
      cin >> s;
      cout << query(s) << endl;
    }
  }
  
  return 0;
}

缺点是每次查询后数组重置时容易TLE，解决方法为只清空使用的部分

结构体实现

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
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> PII;
const int N = 63;
const double pi = acos(-1.0);
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const double eps = 1e-6;
int t;
struct trieNode{
  char val;
  int cnt;
  trieNode** son;
  trieNode(char c){
    val =c;
    son = new trieNode*[N];
    for (int i = 0;i<N;i++) son[i]=nullptr;
    cnt = 0;
  }
};
trieNode* root;
int ascii(char c){
  if (c>='a'&& c<='z') return c-'a'+26;
  else if (c>='A'&&c<='Z') return c-'A';
  else return c-'0'+52;
}
void insert(string s){
  trieNode* p = root;
  for (int i = 0;i<s.size();i++){
    int c = ascii(s[i]);
    if (!p->son[c]) p->son[c] = new trieNode(c);
    p = p->son[c];
    p->cnt++;
  }
}
int query(string s){
  trieNode* p = root;
  for (int i = 0;i<s.size();i++){
    int c = ascii(s[i]);
    if (!p->son[c]) return 0;
    p = p->son[c];
  }
  return p->cnt;
}
int main()
{
  ios
  cin >> t;
  while(t--){
    int n,q;
    cin >> n >> q;
    root = new trieNode(' ');
    while(n--){
      string s;
      cin >> s;
      insert(s);
    }
    while(q--){
      string s;
      cin >> s;
      cout << query(s)<<endl;
    }
  }
  
  return 0;
}

缺点是滥用指针容易MLE，解决方法为N开小一点（差点炸的程度）