字典树（小结）

程序员文章站 2024-01-29 14:03:52

...

0.1 字典树

功能：

在数组中找与一个数异或值最大的元素。

支持添加，删除操作，查找操作。

例如：hdu4825

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
#include <set>
#include <ctype.h>
#include <cmath>
#include <queue>
#include <stack>
using namespace std;
typedef long long ll;
const int MAX = 35*1e5+5;
ll a[MAX];
int root,tot,Next[MAX][2],cnt[MAX];
ll End[MAX];
int Newnode()
{
	memset(Next[tot],-1,sizeof(Next[tot]));
	cnt[tot] = 0;
	End[tot] = 0;
	return tot ++;
}

void Init()
{
	tot = 0;
	root = Newnode();
}

void Insert(ll x)
{
	int p = root;
	cnt[p] ++;
	for(int i = 32; i >= 0; i--)
	{
    	int idx = ((1LL<<i)&x) ? 1 : 0;
		if(Next[p][idx]  == -1)
		{
			Next[p][idx] = Newnode();
		}
			p = Next[p][idx];
			cnt[p] ++;
		}
		End[p] = x;
	}

void Del(ll x)
{
	int p = root;
	cnt[p]--;
	for(int i = 32; i>=0 ; i--)
	{
		int idx = ((1LL<<i)&x)?1:0;
		p = Next[p][idx];
		cnt[p]--;
		}
}

ll Search(ll x)
{
	int p = root;
	for(int i = 32; i>=0 ; i--)
	{
    	int idx = ((1LL<<i)&x)?1:0;
		if(idx == 0)
		{
			if(Next[p][1] != -1 && cnt[Next[p][1]])
			    p = Next[p][1];
			else
			    p = Next[p][0];
		}
		else
		{
			if(Next[p][0] != -1 && cnt[Next[p][0]])
			    p = Next[p][0];
			else
			    p = Next[p][1];
		}
	}
	return End[p];
}
int main()
{
    int t;
    scanf("%d",&t);
    int cas = 1;
    while(t--)
    {
    	Init();
    	int n,m,ma = 0;
    	scanf("%d%d",&n,&m);
    	for(int i = 0; i < n; i++)
    	{
    		scanf("%lld",&a[i]);
    		Insert(a[i]);
    	}
    	printf("Case #%d:\n",cas++);
    	while(m--)
    	{
    		ll x;
    		scanf("%lld",&x);
    		int ans = Search(x);
    		printf("%d\n",ans);
    	}
    }
	return 0;
}

单词字典树

输入n个单词，m个查询，求查询的单词是否出现，几次，或者是否以前缀形式出现

数据量小也可用map 解决

如https://qduoj.com/problem/2

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
#include <set>
#include <ctype.h>
#include <cmath>
#include <queue>
#include <stack>
using namespace std;
typedef long long ll;
const int MAX = 100*1e3+5;    // 每个数分32个..

int root,tot,Next[MAX][30],cnt[MAX];
int Newnode()
{
	memset(Next[tot],-1,sizeof(Next[tot]));
	cnt[tot] = 0;
	return tot ++;
}

void Init()
{
	tot = 0;
	root = Newnode();
}

int getid(char ch)
{
	if(ch == '*') return 26;
	if(ch == '?') return 27;
	return ch-'a';
}

int isover(char s[])
{
	for(int i = 0; s[i]; i++)
		if(s[i] != '*') return 0;
	return 1;
}

void Insert(int p,char s[])
{
	if(s[0] == 0)
	{
		cnt[p] = 1;
		return;
	}
	int id = getid(s[0]);
	if(Next[p][id] == -1)
	{
		Next[p][id] = Newnode();
	}
	if(isover(s)) cnt[p] = 1;
	Insert(Next[p][id],s+1);
}

int Search(int p,char s[])
{
	if(s[0] == 0)
	{
		return cnt[p] != 0;
	}
	int id = getid(s[0]);
	if(Next[p][id] != -1)
	{
		if(Search(Next[p][id],s+1)) return 1;
	}
	if(Next[p][27] != -1)
	{
		if(Search(Next[p][27],s+1)) return 1;
	}
	if(Next[p][26] != -1)
	{
		int len = strlen(s);
		for(int i = 0; i <= len; i++)
		{
		    if(Search(Next[p][26],s+i)) return 1;
		}
	}
	return 0;
}
char s[1005];
int main()
{
    int t;
    scanf("%d",&t);
    int cas = 1;
    while(t--)
    {
		int n,m;
		Init();
		scanf("%d%d",&n,&m);
		for(int i = 0;i < n; i++)
		{
			scanf("%s",s);
			Insert(root,s);
		}
		printf("Case #%d:\n",cas++);
		for(int i = 0; i < m ;i++)
		{
			int yes;
			scanf("%s",s);
			yes = Search(root,s);
			printf("%d",yes);
		}
		puts("");
    }
	return 0;
}

再比如hdu2846后缀字典树，查询的是某单词是字典中几个单词的子串，，后缀加排除重复，如果问的是子串出现的·次数，就不用排重

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
#include <set>
#include <ctype.h>
#include <cmath>
#include <queue>
#include <stack>
using namespace std;
typedef long long ll;
const int MAX = 25*1e5+5;   

int root,tot,Next[MAX][30],cnt[MAX],of[MAX];
int Newnode()
{
	memset(Next[tot],-1,sizeof(Next[tot]));
	cnt[tot] = 0;
	of[tot] = 0;
	return tot ++;
}

void Init()
{
	tot = 0;
	root = Newnode();
}

int getid(char ch)
{
	return ch-'a';
}

void Insert(int p,char s[],int cur)
{
	if(s[0] == 0)
	{
		if(of[p] != cur)
	    {
		    cnt[p]++;
		    of[p] = cur;
	    }
		return;
	}
	int id = getid(s[0]);
	if(Next[p][id] == -1)
	{
		Next[p][id] = Newnode();
	}
	if(of[p] != cur)    // 防止字典中的一个单词重复记录某个子串
	{
		cnt[p]++;
		of[p] = cur;
	}
	Insert(Next[p][id],s+1,cur);
}

int Search(int p,char s[])
{
	if(s[0] == 0)
	{
		return cnt[p];
	}
	int id = getid(s[0]);
	if(Next[p][id] != -1)
	{
		return Search(Next[p][id],s+1);
	}
	return 0;
}
char s[1005];
char str[1005];
map <string,bool> mp;
int main()
{
	int n;
	scanf("%d",&n);
	Init();
	for(int i = 1; i <= n; i++)
	{
		scanf("%s",s);
		for(int j = 0; s[j]; j++)
		{
			Insert(root,s+j,i);
		}
	}
	int m;
	scanf("%d",&m);
	while(m--)
	{
		scanf("%s",s);
		printf("%d\n",Search(root,s));
	}
	return 0;
}

hdu 1305 求给定字符串数组某个元素是否是某个其它元素的前缀，，保存所有前缀，查询每个单词，看出现次数是否均为1

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
#include <set>
#include <ctype.h>
#include <cmath>
#include <queue>
#include <stack>
using namespace std;
typedef long long ll;
const int MAX = 25*1e5+5;

int root,tot,Next[MAX][3],cnt[MAX];
int Newnode()
{
	memset(Next[tot],-1,sizeof(Next[tot]));
	cnt[tot] = 0;
	return tot ++;
}

void Init()
{
	tot = 0;
	root = Newnode();
}

int getid(char ch)
{
	return ch-'0';
}

void Insert(int p,char s[])
{
	if(s[0] == 0)
	{
		cnt[p]++;
		return;
	}
	int id = getid(s[0]);
	if(Next[p][id] == -1)
	{
		Next[p][id] = Newnode();
	}
	cnt[p] ++;
	Insert(Next[p][id],s+1);
}

int Search(int p,char s[])
{
	if(s[0] == 0)
	{
		return cnt[p];
	}
	int id = getid(s[0]);
	if(Next[p][id] != -1)
	{
		return Search(Next[p][id],s+1);
	}
	return 0;
}
char s[10005][20];
int main()
{
	int k = 0;
	int cas = 1;
	Init();
	while(scanf("%s",s[k])!=EOF)
	{
		if(!strcmp(s[k],"9"))
		{
			int yes = 1;
			for(int i = 0; i < k; i++)
			{
			//	puts(s[i]);
			///	cout <<Search(root,s[i]) <<endl;
				if(Search(root,s[i]) >= 2)
				{
					yes = 0;
				    break;
				}
			}
			if(yes) printf("Set %d is immediately decodable\n",cas++);
			else printf("Set %d is not immediately decodable\n",cas++);
			Init();
			k = 0;
		}
		else
		{
			Insert(root,s[k++]);
		}
	}
	return 0;
}

HDU1247-Hat’s Words：

这个可以先把单词存好，逐个查询，枚举分点，注意一个单词可以有两个一样的单词组成，，，如 aa 这种情况，如过数组有一个a就可以了.......

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
#include <set>
#include <ctype.h>
#include <cmath>
#include <queue>
#include <stack>
using namespace std;
typedef long long ll;
const int MAX = 25*1e5+5;

int root,tot,Next[MAX][30],cnt[MAX];
int Newnode()
{
	memset(Next[tot],-1,sizeof(Next[tot]));
	cnt[tot] = 0;
	return tot ++;
}

void Init()
{
	tot = 0;
	root = Newnode();
}

int getid(char ch)
{
	return ch-'a';
}

void Insert(int p,char s[])
{
	if(s[0] == 0)
	{
		cnt[p]++;
		return;
	}
	int id = getid(s[0]);
	if(Next[p][id] == -1)
	{
		Next[p][id] = Newnode();
	}
	Insert(Next[p][id],s+1);
}

int Search(int p,char s[])
{
	if(s[0] == 0)
	{
		return cnt[p];
	}
	int id = getid(s[0]);
	if(Next[p][id] != -1)
	{
		return Search(Next[p][id],s+1);
	}
	return 0;
}
char s[50005][500];
char str[500];
int main()
{
	int k = 0;
	Init();
	while(scanf("%s",s[k])!=EOF)
	{
		Insert(root,s[k]);
		k++;
	}
	for(int i = 0; i < k; i++)
	{
		int len = strlen(s[i]);
		for(int j = 0; j < len-1; j++)
		{
			str[j] = s[i][j];
			str[j+1] = 0;
			if(Search(root,str) >= 1 && Search(root,&s[i][j+1]) >= 1)
			{
				puts(s[i]);
				break;
			}
		}
	}
	return 0;
}

上一篇： OPPO CEO陈明永：500亿元进军IoT 或涉足智慧屏、机器人

下一篇：优麒麟开源系统UKUI 3.0预告：全新的开始菜单

字典树（小结）

[jry线段树]小结

虚树学习小结

[OI]主席树小结

字典树小结

线段树小结

字典树（小结）

javascript trie前缀树的示例

用户登录之cookie信息安全小结

CSS 小结笔记之盒子模型

如何创建环型、树型双层布局