字典树 Trie

Cifera_meow · 2024-01-24 10:10:06 · 个人记录

字典树，一种处理字符前缀的算法，可以高效处理求以这一串字符为前缀的字符数量，以及字符补全问题。

假定现在有两个字符AAA和AAB，要用字典数存储，存储结果就是这样的：

 root
  |
  A
  |
  A
  |\
  A B

这样，只需要从根节点（root）往下找，就能迅速匹配一个字符（或者半个？）

字典树一般会存点，我这里选用结构体存

首先，每个点必须有26条出边表示a - z的边，开一个数组来存，数组中的内容即其指向的点。

但是！还有一个问题！

如果我要存ABCD和ABC，那这个ABC就存了个寂寞

所以，每个点还应该有一个Words变量，表示该节点往下走还能组成多少单词

这样就能解决单词重复或包含问题

总而言之，结构体长这样：

struct dot{
    int Words;
    int Chr[30]; 
}d[500005];

然后就是

建树

建树时，只需要按照字符串中的字符顺序往下找，如果有这个点就走到这个点上，没有就新建一个点并走到这个点上即可

记得边走边给路径上的点加Words

void build(int dot,string s){
    for(int i=0;i<s.length();i++){
        d[dot].Words++;
        if(d[dot].Chr[s[i]-'0'] != 0)dot = d[dot].Chr[s[i]-'0'];
        else{
            d[dot].Chr[s[i]-'0'] = ++cnt;
            dot = cnt;
        }
    }
    d[dot].Words++;
}

接下来

查询

和建树类似，只不过找不到就返回false即可

bool find(int dot,string s){
    for(int i=0;i<s.length();i++){
        dot = d[dot].Chr[s[i]-'0'];
        if(dot == 0)return false;
    }
    return true;
}

例题：

ABC287E Karuta

这是我认识字典树的第一题，这个比较复杂，要求每个字符串的公共前缀，但其实不难，在找的时候如果发现只剩这一个字符串了，前半段就是公共前缀，这时我们记录的Words就发挥作用了

代码

#include<bits/stdc++.h>
using namespace std;
struct dot{
    int Words;
    int Chr[30]; 
}d[500005];
int n,cnt = 1;
string s[500005];
void build(int dot,string s){
    for(int i=0;i<s.length();i++){
        d[dot].Words++;
        if(d[dot].Chr[s[i]-'a'] != 0)dot = d[dot].Chr[s[i]-'a'];
        else{
            d[dot].Chr[s[i]-'a'] = ++cnt;
            dot = cnt;
        }
    }
    d[dot].Words++;
}
int find(int dot,string s){
    for(int i=0;i<s.length();i++){
        dot = d[dot].Chr[s[i]-'a'];
        if(d[dot].Words == 1)return i;
    }
    return s.length();
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        cin >> s[i];
        build(1,s[i]);
    }
    for(int i=1;i<=n;i++){
        printf("%d\n",find(1,s[i]));
    }
    return 0;
} 

感谢复习