Trie树——字符串的插入和查找

时间:2022-12-30 14:44:25

如果给定n个字符串,要你在其中寻找字符串s

思路:

  1. 暴力算法:挨个比较,直到找出O(nm)
  2. 如何让他的复杂度变回线性呢,就要用到Trie树了
  3. 建立一个树,每个节点对应一个编号,表示一个字母,如果要在这个节点下再加入一个字母,则节点编号数++——用ch[i][a]表示一条边,i是父亲节点的编号,a是一个字母,如果父亲对这个字母有连边,ch[i][a] = sz(编号)++,所以ch[i][a]对应字母a的编号,继续插入时从sz继续讨论
  4. 当一个字符串插入完成后,在这个字符串的最后字母上加上附加值,表示这个字母是一个字符串的终点,当附加值==0时,表示他不是任何字符串的终点,这个附加值可以是字符串的标号

建成的树如图(出自刘汝佳《算法竞赛入门经典训练指南》)
Trie树——字符串的插入和查找

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 2000 + 10;
int d[MAXN];

//字母表为全体小写字母的Trie
struct Trie
{
int sz;
int ch[MAXN][26];
void clear() { sz = 1; memset(ch[0], 0, sizeof(ch[0])); sz = 1;} // 初始时只有一个根结点
int val[MAXN];


int cal(char a) { return a - 'a';}

// 插入字符串s,附加信息为v。注意v必须非0,因为0代表“本结点不是单词结点”
void insert(const char *s, int v)
{
int u = 0;
int n = strlen(s);
for(int i = 0; i < n; i++)
{
int c = cal(s[i]);
if(!ch[u][c]) // 结点不存在
{
memset(ch[sz], 0, sizeof(ch[sz])); //相当于申请新的内存空间(把即将加入的节点编号初始化)
val[sz] = 0; // 中间结点的附加信息为0
ch[u][c] = sz++; // 新建结点
}
u = ch[u][c]; // 往下走
}
val[u] = v; // 字符串的最后一个字符的附加信息为v
}

//找出字符串s并返回它的附加信息
int find(const char *s) //查找
{
int u = 0;
int n = strlen(s);
for(int i = 0; i < n; i++)
{
int c = cal(s[i]);
if(ch[u][c]) u = ch[u][c]; //如果下一个字符在树中,往下走
else return 0;
}
if(!val[u]) return 0; //如果最后一个字符没有附加信息,则没有该字符串
else return val[u];
}

};

Trie trie;

char str[MAXN];

int main()
{
trie.clear();
while(scanf("%s", str) == 1)
{
trie.insert(str, 3);
cout << trie.find(str) << endl;
}

return 0;
}