字典树(Trie)

字典树简介

字典树(Trie)，又称为前缀树，和编译原理里面的DFA很像。它长下面这个样子

模板

int tree[maxn][30]; //字典树，有maxn个结点，30表示字符集的大小，比如小写字母就26个
int isend[maxn]; //表示结点i是否为某个串的结尾
int tot; //节点数

void insert(char *s)
{
        // 根节点为0号结点
	int root=0, len=strlen(s);
	for(int i=0;i<len;i++)
	{
	        // pos是指当前字符应该为root的哪一个儿子
		int pos = s[i]-'a';
		// 如果不存在，则新创建
		if(!tree[root][pos])
			tree[root][pos] = ++tot;
		// root往下走
		root = tree[root][pos];
	}
	// 标记当前编号的结点是某个字符串的结尾
	isend[root] = 1;
}

int find(char *s)
{
	int root=0, len=strlen(s);
	for(int i=0;i<len;i++)
	{
		int pos = s[i]-'a';
		root = tree[root][pos];
		// 不存在则返回0
		if(!root)return 0;
	}
	return 1;
}

代码挺简单的，没什么讲的

例题

Hdu1671

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define IO ios::sync_with_stdio(0)
typedef pair<int, int> P;
const int maxn = 1e5+5;
const ll mod = 1e9+7;
using namespace std;


int tree[maxn][10];
int cnt[maxn], isend[maxn];
int tot;

bool insert(char *s)
{
	int root = 0;
	int len = strlen(s);
	for(int i=0;i<len;i++)
	{
		int pos = s[i]-'0';
		if(!tree[root][pos])
			tree[root][pos] = ++tot;
		root = tree[root][pos];
		cnt[root]++;
		if(cnt[root]>1 && isend[root])return false;
	}
	isend[root] = 1;
	return (cnt[root]>1&&isend[root]) ? false : true;
}

int main()
{
	int t;
	scanf("%d", &t);
	while(t--)
	{
		int n;
		scanf("%d", &n);
		memset(tree, 0, sizeof(tree));
		memset(cnt, 0, sizeof(cnt));
		memset(isend, 0, sizeof(isend));
		tot = 0;
		int f = 1;
		for(int i=1;i<=n;i++)
		{
			char s[15];
			scanf("%s", s);
			if(!insert(s))f=0;
		}
		if(f)cout<<"YES\n";
		else cout<<"NO\n";
	}
	return 0;
}

Hdu1251

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define IO ios::sync_with_stdio(0)
typedef pair<int, int> P;
const int maxn = 4e5+5;
const ll mod = 1e9+7;
using namespace std;

int tree[maxn][30];
int cnt[maxn];
int tot;

void insert(char *s)
{
	int root=0, len=strlen(s);
	for(int i=0;i<len;i++)
	{
		int pos = s[i]-'a';
		if(!tree[root][pos])
			tree[root][pos] = ++tot;
		root = tree[root][pos];
		cnt[root]++;
	}
}

int find(char *s)
{
	int root=0, len=strlen(s);
	for(int i=0;i<len;i++)
	{
		int pos = s[i]-'a';
		root = tree[root][pos];
		if(!root)return 0;
	}
	return cnt[root];
}

int main()
{
	char s[15];
	while(gets(s) && s[0]!='\0')
		insert(s);
	while(gets(s))
		printf("%d\n", find(s));
	return 0;
}