Trie（字典树）

时间：2023-03-09 19:49:26
Trie（字典树）

没时间整理了，老吕又讲课了@ @

概念

Trie即字典树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种，典型应用是统计和排序大量的字符串（不限于字符串）

Trie字典树主要用于存储字符串，Trie 的每个 Node 保存一个字符。用链表来描述的话，就是一个字符串就是一个链表。每个 Node 都保存了它的所有子节点。

基本操作

插入 查找 前缀查询 删除

实质：空间换时间

eg:

插入单词：a,ab,abc,abd,acb

Trie（字典树）

瞅个板子

给定 \(n\) 个长度不超过 \(10\) 的数字串，问其中是否存在两个数字串 \(S,T\)，使得 \(S\) 是 \(T\) 的前缀

hash:时间复杂度起飞

这不显然是字典树的板子么

#include <iostream>

#include <cstdio>

#include <queue>

#include <cstring>

#include <string>

#include <cmath>

#include <map>

using namespace std;

const int A = 1e3 + 2;

const int B = 1e4 + 2;

const int C = 1e5 + 5;

const int D = 2e6 + 5;

const int inf = 0x3f3f3f3f;

const int mod = 99984198447;

int read(){

	int x = 0,f = 1;char c = getchar();

	while(c < '0'||c > '9'){if(c == '-')f = -1;c = getchar();}

	while(c >= '0'&&c <= '9'){x = x*10 + c - '0';c = getchar();}

	return x*f;

}

int T, n, tree[C][11],cnt;

bool vis[C],ans;

char s[50];

bool insert(char * s){

   int len = strlen(s),u = 1;

   bool flag = false;

   for(int i = 0;i < len; i++){

   	   int num = s[i] - '0';

   	   if(!tree[u][num])

   	   	tree[u][num] = ++cnt;//如果没有这个字母，就新建一个点 

   	   else if(i == len - 1) flag = true;//如果单词在字典树中能找到(即字典树中恰好有这个单词)

   	   u = tree[u][num];//从新建的点后者原来的点向下走，继续寻找

   	   if(vis[u])flag = true;//字典中的单词为新填的单词的前缀

   }

   vis[u] = true;//将单词的最后一个字母在字典树中打上标记

   return flag;

}

void clear(){//注意清零

    cnt = 1;

	memset(vis, 0,sizeof(vis));

   	memset(tree, 0,sizeof(tree));

    ans = false;

}

int main(){

   T =  read();

   while(T--){

      n = read();

	  clear();

   	for(int i = 1;i <= n; i++){

   	  	  scanf("%s", s);

   	  	  if(insert(s))ans = true;

	  }

	 if(!ans)printf("YES\n");

	 else printf("NO\n");

   }

}

相关文章