`
Dev|il
  • 浏览: 126100 次
  • 性别: Icon_minigender_1
  • 来自: 成都
社区版块
存档分类
最新评论

Trie树(单词查找树或键树)

 
阅读更多
Trie树

  Trie树,又称单词查找树或键树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:最大限度地减少无谓的字符串比较,查询效率比哈希表高。
   Trie是一颗存储多个字符串的树。相邻节点间的边代表一个字符,这样树的每条分支代表一则子串,而树的叶节点则代表完整的字符串。和普通树 不同的地方是,相同的字符串前缀共享同一条分支。还是例子最清楚。给出一组单词,inn, int, at, age, adv, ant, 我们可以得到下面的Trie:


tire树的查找时间复杂度为O(n)
实现代码(借鉴了某位博主的代码):
#include <iostream>
using namespace std;

const int branch = 26; //定义分支

typedef struct Trie_Node{
	bool isStr; //判断此处是否构成一个串
	struct Trie_Node *next[branch]; //指向各个指数的指针
	Trie_Node(): isStr(false)
	{
		memset(next, NULL, sizeof(next)); //对各个分支初始化
	}
}*pTrie_Node;


class Trie{
private:
	pTrie_Node root; //根
public:
	Trie();
	void insert(const char *word);
	bool search(char *word);
	void destory(pTrie_Node root);
};

Trie::Trie()
{
	this->root = new Trie_Node();
}
//插入结点
void Trie::insert(const char *word)
{
	pTrie_Node loc = this->root;
	while(*word)
	{
		if(loc->next[*word - 'a'] == NULL) //不存在则建立
		{
			pTrie_Node tmp = new Trie_Node();
			loc->next[*word - 'a'] = tmp;
		}
		loc = loc->next[*word - 'a'];
		word++;
	}
	loc->isStr = true; //标识此处有个字符串
}

bool Trie::search(char *word)
{
	pTrie_Node loc = this->root;
	while(*word && loc)
	{
		loc = loc->next[*word - 'a'];
		word++;
	}
	return (loc != NULL && loc->isStr);
}

void Trie::destory(pTrie_Node cur)
{
	for(int i = 0; i < branch; i++)
		if(cur->next[i] != NULL)
			destory(cur->next[i]);
	delete cur;
}

int main()
{
	Trie t;
	t.insert("a");
	t.insert("abc");
	if(t.search("abcd"))
		cout<<"存在"<<endl;
	return 0;
}


下面是tire树的题目:
http://acm.hdu.edu.cn/showproblem.php?pid=1251
统计难题

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 131070/65535 K (Java/Others)
Total Submission(s): 7502    Accepted Submission(s): 2902


Problem Description
Ignatius最近遇到一个难题,老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).



Input
输入数据的第一部分是一张单词表,每行一个单词,单词的长度不超过10,它们代表的是老师交给Ignatius统计的单词,一个空行代表单词表的结束.第二部分是一连串的提问,每行一个提问,每个提问都是一个字符串.

注意:本题只有一组测试数据,处理到文件结束.



Output
对于每个提问,给出以该字符串为前缀的单词的数量.



Sample Input
banana
band
bee
absolute
acm

ba
b
band
abc


Sample Output
2
3
1
0

AC代码:
#include <iostream>
using namespace std;

const int branch = 26;

typedef struct trie_Node{
	bool isStr;
	struct trie_Node *next[branch];
	trie_Node():isStr(false)
	{
		memset(next, NULL, sizeof(next));
	}
}*pTrie_Node;

class Trie{
private:
	pTrie_Node root;
public:
	Trie()
	{
		root = new trie_Node();
	}
	void insert(const char *word);
	int search(const char *prefix);
	void find(pTrie_Node cur, int &cnt);
};

void Trie::insert(const char *word)
{
	pTrie_Node loc = root;
	while(*word)
	{
		if(loc->next[*word - 'a'] == NULL)
		{
			pTrie_Node tmp = new trie_Node();
			loc->next[*word - 'a'] = tmp;
		}
		loc = loc->next[*word - 'a'];
		word++;
	}
	loc->isStr = true;
}

int Trie::search(const char *prefix)
{
	pTrie_Node loc = root;
	int cnt = 0;
	while(*prefix && loc)
	{
		loc = loc->next[*prefix - 'a'];
		prefix++;
	}
	if(loc != NULL)
		find(loc, cnt);
	return cnt;
}

void Trie::find(pTrie_Node cur, int &cnt)
{
	if(cur->isStr)
		cnt++;
	for(int i = 0; i < branch; i++)
	{
		if(cur->next[i] != NULL)
			find(cur->next[i], cnt);
	}
}
int main()
{
	char str[15];
	Trie t;
	while(cin.getline(str, 11))
	{
		if(str[0] == '\0')
			break;
		t.insert(str);
	}
	while(cin>>str)
	{
		cout<<t.search(str)<<endl;
	}
	return 0;
}


http://acm.hdu.edu.cn/showproblem.php?pid=2222
Keywords Search

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 11008    Accepted Submission(s): 3825


Problem Description
In the modern time, Search engine came into the life of everybody like Google, Baidu, etc.
Wiskey also wants to bring this feature to his image retrieval system.
Every image have a long description, when users type some keywords to find the image, the system will match the keywords with description of image and show the image which the most keywords be matched.
To simplify the problem, giving you a description of image, and some keywords, you should tell me how many keywords will be match.



Input
First line will contain one integer means how many cases will follow by.
Each case will contain two integers N means the number of keywords and N keywords follow. (N <= 10000)
Each keyword will only contains characters 'a'-'z', and the length will be not longer than 50.
The last line is the description, and the length will be not longer than 1000000.



Output
Print how many keywords are contained in the description.


Sample Input
1
5
she
he
say
shr
her
yasherhs


Sample Output
3


Author
Wiskey

题意:输出,以上字符串序列在目标串中匹配的个数
#include <iostream>
using namespace std;

const int branch = 26;
const int _N = 10005;


char desc[1000005];
char keyword[55];
/*注意两点:
第一组数据:
abc
abcabcabcabcabc
输入1
第二组数据
2
a
a
a
上面这组数据是输出2,不是1
*/
typedef struct trie_Node{
	bool isStr;
	bool isMatch; //记录是否匹配过
	int cnt; //记录单词的个数
	struct trie_Node *next[branch];
	trie_Node():isStr(false),isMatch(false), cnt(0)
	{
		memset(next, NULL, sizeof(next));
	}
}*pTrie_Node;

class Trie{
private:
	pTrie_Node root;
public:
	Trie()
	{
		root = new trie_Node();
	}
	void insert(const char *word);
	int search(const char *keyword);
};

void Trie::insert(const char *word)
{
	pTrie_Node loc = root;
	while(*word)
	{
		if(loc->next[*word - 'a'] == NULL)
		{
			pTrie_Node tmp = new trie_Node();
			loc->next[*word - 'a'] = tmp;
		}
		loc = loc->next[*word - 'a'];
		word++;
	}
	loc->cnt++;
	loc->isStr = true;
}

int Trie::search(const char *keyword)
{
	int cnt = 0;
	pTrie_Node loc = root;
	while(*keyword && loc)
	{
		loc = loc->next[*keyword - 'a'];
		if(loc != NULL && loc->isStr && !loc->isMatch)
		{
			cnt += loc->cnt;
			loc->isMatch = true;
		}
		keyword++;
	}
	return cnt;
}


int main()
{
	int cas, n, i, cnt, len;
	cin>>cas;
	while(cas--)
	{
		cin>>n;
		Trie t;
		for(i = 0; i < n; i++)
		{
			cin>>keyword;
			t.insert(keyword);
		}
		cin>>desc;
		len = strlen(desc);
		cnt = 0;
		for(i = 0; i < len; i++)
			if(cnt < n)
				cnt += t.search(&desc[i]);
			else
				break;
		cout<<cnt<<endl;
	}
	return 0;
}

AC自动机代码:
#include <iostream>
#include <queue>
using namespace std;

const int branch = 26;
char desc[1000005];
char keyword[55];

typedef struct trie_node{
	bool isword;
	int words;
	struct trie_node *fail;
	struct trie_node *next[branch];
	trie_node():isword(false), fail(NULL), words(0)
	{
		memset(next, NULL, sizeof(next));
	}
}*pTrie_Node;

class ACTrie{
private:
	pTrie_Node root;
public:
	ACTrie()
	{
		root = new trie_node();
	}
	pTrie_Node getRoot()
	{
		return root;
	}
	void insert(const char *word);
	void build_ac_automation();
	int search(const char *desc);
	void destory(pTrie_Node);
};

void ACTrie::insert(const char *word)
{
	pTrie_Node loc = root;
	while(*word && loc)
	{
		if(loc->next[*word - 'a'] == NULL)
			loc->next[*word - 'a'] = new trie_node();
		loc = loc->next[*word - 'a'];
		word++;
	}
	loc->words++;
	loc->isword = true;
}

void ACTrie::build_ac_automation()
{
	int i;
	queue<pTrie_Node> q;
	pTrie_Node p, temp;
	q.push(root);
	while(!q.empty())
	{
		temp = q.front();
		q.pop();
		for(i = 0; i < branch; i++)
			if(temp->next[i])
			{
				if(temp == root)
					temp->next[i]->fail = root;
				else
				{
					p = temp->fail;
					while(p)
					{
						if(p->next[i] != NULL)
						{
							temp->next[i]->fail = p->next[i];
							break;
						}
						p = p->fail;
					}
					if(!p)
						temp->next[i]->fail = root;
				}
				q.push(temp->next[i]);
			}
	}
}

int ACTrie::search(const char *desc)
{
	pTrie_Node loc = root;
	int index, cnt = 0;
	while(*desc)
	{
		index = *desc - 'a';
		while(!loc->next[index] && loc != root)
			loc = loc->fail;
		loc = loc->next[index];
		loc = !loc ? root : loc;
		pTrie_Node temp = loc;
		while(temp != root && temp->isword)
		{
			cnt += temp->words;
			temp->isword = false;
			temp = temp->fail;
		}
		desc++;
	}
	return cnt;
}
void ACTrie::destory(pTrie_Node cur)
{
	for(int i = 0; i < branch; i++)
		if(cur->next[i] != NULL)
			destory(cur->next[i]);
	delete cur;
}
int main()
{
	int cas, n, i;
	cin>>cas;
	while(cas--)
	{
		ACTrie t;
		cin>>n;
		for(i = 0; i < n; i++)
		{
			cin>>keyword;
			t.insert(keyword);
		}
		t.build_ac_automation();
		cin>>desc;
		cout<<t.search(desc)<<endl;
		t.destory(t.getRoot());
	}
	return 0;
}

http://acm.hdu.edu.cn/showproblem.php?pid=1075
What Are You Talking About

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 102400/204800 K (Java/Others)
Total Submission(s): 5008    Accepted Submission(s): 1500


Problem Description
Ignatius is so lucky that he met a Martian yesterday. But he didn't know the language the Martians use. The Martian gives him a history book of Mars and a dictionary when it leaves. Now Ignatius want to translate the history book into English. Can you help him?



Input
The problem has only one test case, the test case consists of two parts, the dictionary part and the book part. The dictionary part starts with a single line contains a string "START", this string should be ignored, then some lines follow, each line contains two strings, the first one is a word in English, the second one is the corresponding word in Martian's language. A line with a single string "END" indicates the end of the directory part, and this string should be ignored. The book part starts with a single line contains a string "START", this string should be ignored, then an article written in Martian's language. You should translate the article into English with the dictionary. If you find the word in the dictionary you should translate it and write the new word into your translation, if you can't find the word in the dictionary you do not have to translate it, and just copy the old word to your translation. Space(' '), tab('\t'), enter('\n') and all the punctuation should not be translated. A line with a single string "END" indicates the end of the book part, and that's also the end of the input. All the words are in the lowercase, and each word will contain at most 10 characters, and each line will contain at most 3000 characters.



Output
In this problem, you have to output the translation of the history book.



Sample Input
START
from fiwo
hello difh
mars riwosf
earth fnnvk
like fiiwj
END
START
difh, i'm fiwo riwosf.
i fiiwj fnnvk!
END


Sample Output
hello, i'm from mars.
i like earth!

Hint
Huge input, scanf is recommended.

题意:第一个START到END之间是字典表,前面代表原词,后面代表火星文,现在给你一个句子,里面有火星文,请翻译句子
/*
这题要注意一点,在搜索过程中,被搜索的是否是在字典里面是一个单词
比如 在字典里面
like abcabc
而句子里面有一个abc 这样搜索过程中也会输出空白
if(loc != NULL && loc->isword) 
		cout<<loc->wd;
因为这个问题 wa了一次,注意
*/
#include <iostream>
using namespace std;

const int branch = 26;
char st[3005];
typedef struct trie_Node{
	bool isword;
	char wd[15];
	struct trie_Node *next[branch];
	trie_Node() : isword(false)
	{
		memset(next, NULL, sizeof(next));
	}
}*pTrie_Node;

class Trie{
private:
	pTrie_Node root;
public:
	Trie()
	{
		root = new trie_Node();
	}
	void insert(const char *word, const char *oldword);
	bool search(const char *word);
};

void Trie::insert(const char *word, const char *oldword)
{
	pTrie_Node loc = root;
	while(*word && loc)
	{
		if(loc->next[*word - 'a'] == NULL)
		{
			pTrie_Node tmp = new trie_Node();
			loc->next[*word - 'a'] = tmp;
		}
		loc = loc->next[*word - 'a'];
		word++;
	}
	strcpy(loc->wd, oldword);
	loc->isword = true;
}

bool Trie::search(const char *word)
{
	pTrie_Node loc = root;
	while(*word && loc)
	{
		loc = loc->next[*word - 'a'];
		word++;
	}
	if(loc != NULL && loc->isword) 
		cout<<loc->wd;
	else
		return false;
	return true;
}
int main()
{
	Trie t;
	char oldword[15], word[15];
	int i, j, len;
	cin>>oldword;
	while(cin>>oldword)
	{
		if(!strcmp(oldword, "END"))
			break;
		cin>>word;
		t.insert(word, oldword);
	}
	cin>>oldword;
	getchar();
	while(cin.getline(st, 3005))
	{
		if(!strcmp(st, "END"))
			break;
		len = strlen(st);
		word[0] = '\0';
		for(i = 0, j = 0; i < len; i++)
		{
			if(st[i] >= 'a' && st[i] <= 'z')
				word[j++] = st[i];
			else
			{
				word[j] = '\0';
				if(word[0] != '\0')
					if(!t.search(word))
						cout<<word;
				cout<<st[i];
				j = 0;
			}
		}
		cout<<endl;
	}
	return 0;
}

http://acm.hdu.edu.cn/showproblem.php?pid=1671
Phone List

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3374    Accepted Submission(s): 1113


Problem Description
Given a list of phone numbers, determine if it is consistent in the sense that no number is the prefix of another. Let’s say the phone catalogue listed these numbers:
1. Emergency 911
2. Alice 97 625 999
3. Bob 91 12 54 26
In this case, it’s not possible to call Bob, because the central would direct your call to the emergency line as soon as you had dialled the first three digits of Bob’s phone number. So this list would not be consistent.



Input
The first line of input gives a single integer, 1 <= t <= 40, the number of test cases. Each test case starts with n, the number of phone numbers, on a separate line, 1 <= n <= 10000. Then follows n lines with one unique phone number on each line. A phone number is a sequence of at most ten digits.


Output
For each test case, output “YES” if the list is consistent, or “NO” otherwise.


Sample Input
2
3
911
97625999
91125426
5
113
12340
123440
12345
98346


Sample Output
NO
YES


题意:大致含义是说输入的串中,任何一个串不能是另外一个串的字串
#include <iostream>
using namespace std;

const int branch = 10;

//注意点:记得每次释放字典树,因为为多个用例

typedef struct trie_Node{
	bool isword;
	struct trie_Node *next[branch];
	trie_Node() : isword(false)
	{
		memset(next, NULL, sizeof(next));
	}
}*pTrie_Node;

class Trie{
private:
	pTrie_Node root;
public:
	Trie()
	{
		root = new trie_Node();
	}
	pTrie_Node getRoot()
	{
		return root;
	}
	void insert(const char *word);
	bool search(pTrie_Node cur);
	void destory(pTrie_Node cur);
};

void Trie::insert(const char *word)
{
	pTrie_Node loc = root;
	while(*word && loc)
	{
		if(loc->next[*word - '0'] == NULL)
		{
			pTrie_Node tmp = new trie_Node();
			loc->next[*word - '0'] = tmp;
		}
		loc = loc->next[*word - '0'];
		word++;
	}
	loc->isword = true;
}

bool Trie::search(pTrie_Node cur)
{
	int i;
	if(cur->isword)
		for(i = 0; i < branch; i++)
			if(cur->next[i] != NULL)
				return false;
	for(i = 0; i < branch; i++)
		if(cur->next[i] != NULL)
			if(!search(cur->next[i]))
				return false;
	return true;
}

void Trie::destory(pTrie_Node cur)
{
	for(int i = 0; i < branch; i++)
		if(cur->next[i] != NULL)
			destory(cur->next[i]);
	delete cur;
}

int main()
{
	int t, n, i;
	char phone[11];
	cin>>t;
	while(t--)
	{
		cin>>n;
		Trie t;
		for(i = 0; i < n; i++)
		{
			cin>>phone;
			t.insert(phone);
		}
		if(!t.search(t.getRoot()))
			cout<<"NO"<<endl;
		else
			cout<<"YES"<<endl;
		t.destory(t.getRoot()); //这句很重要,不然要超内存
	}
	return 0;
}
  • 大小: 12.7 KB
分享到:
评论

相关推荐

    Go-trie-单词查找树实现Go实现

    在这个背景下,了解并掌握如何在Go中实现Trie(单词查找树)这种数据结构对于提升代码质量具有重要意义。 Trie,又称为前缀树或字典树,是一种用于存储动态集合或关联数组的树形数据结构。它的主要特点是通过键的...

    基于Trie树模仿谷歌百度搜索框提示

    每当用户键入一个字符时,我们会调用Trie树的查找方法,获取所有匹配当前前缀的单词,并将这些单词显示在搜索框下方作为提示。为了优化用户体验,可以设置一个最小的触发字符数,例如3个,避免过多的提示干扰用户。 ...

    trie树的实现(C)

    在trie.c中,关于查找定义了两个函数,一个是find(),一个是search(),二者的区别是,前者仅判断一个字符串是否在树中出现,而后者除了判断字符串是否出现,还会判断待查找的字符串是否是一个合法的单词。

    HASH(Trie)-.rar_HashTree.h_TRIE_hash树_trie树_字典树

    Trie,又被称为前缀树或字典树,是一种用于存储键值对的数据结构,尤其适用于字符串的查找和管理。 **Trie 树基础知识** Trie 树是一种多叉树,每个节点代表一个字符串的前缀。根节点不包含任何字符,而叶子节点则...

    从trie树谈到后缀树

    例如,给定100000个长度不超过10的单词,如果使用Trie树,可以快速判断一个单词是否存在于集合中,并找到其首次出现的位置。使用哈希表虽然也能解决这个问题,但面对前缀查询等复杂需求时,Trie树的优势更为明显。 ...

    Acm Trie树

    **Trie树**,又称为**字典树**或**前缀树**,是一种用于高效存储和检索字符串的树形数据结构。它通过利用字符串之间的公共前缀来减少查询时间,从而提高搜索效率。在诸如文本编辑器、搜索引擎、自动补全等功能中非常...

    Trie树题解1

    利用Trie树,我们可以先构建一个包含所有单词的树,然后对矩阵的每个位置进行深度优先搜索或广度优先搜索,检查当前位置及周围位置组成的字符串是否为树中的单词。 3. POJ2001 - 这题需要找到每个单词的最短前缀,...

    从Trie树(字典树)谈到后缀树.pdf

    Trie树适合解决单词查找以及统计问题,而后缀树则在字符串模式匹配、最长公共子串等问题上有着出色的表现。 首先,Trie树是一种树形结构,用于高效存储和检索字符串数据集中的键。它能够快速查找字符串是否出现以及...

    trie树所有代码,试题打包

    Trie树,又称前缀树或字典树,是一种用于存储字符串的数据结构,它在IT领域尤其是数据结构和算法的学习中占据着重要的地位。这个压缩包包含的“王赟.doc”和“王赟.ppt”很可能是关于Trie树的详细讲解和实践题目,...

    数据结构课设Trie树

    与传统的二叉查找树不同,Trie树以字符串为键,每个节点代表一个字符串的前缀。根节点通常不包含任何字符,而从根节点到叶子节点的路径上的边代表了字符串中的字符,路径上的字符组合起来就是该节点对应的关键字。...

    数据结构实验报告-----trie树

    3. **查找元素**:`SearchString`函数用于查找Trie树中是否存在某个单词。它同样逐字符地遍历单词,检查每个字符对应的子节点,如果遍历到最后一个字符且该节点存在,说明单词存在于Trie树中。 4. **查找单词前缀...

    35丨Trie树:如何实现搜索引擎的搜索关键词提示功能?1

    【Trie树】,又称字典树或前缀树,是一种高效处理字符串匹配的数据结构,常用于搜索引擎的搜索关键词提示功能。它的设计思路是利用字符串之间的公共前缀,将重复的前缀合并,以提高查找效率。在搜索引擎的场景中,...

    Trie树的插入、查询、删除和部分应用(单词的查询、单词出现频率/DFS和非DFS两种遍历)

    在Trie树中,DFS可以用来遍历所有单词或执行特定任务,如找到所有以特定前缀开头的单词。 相反,非深度优先搜索在这里可能指的是广度优先搜索(BFS),它使用队列来遍历所有节点。在Trie树中,BFS通常用于查找最短...

    算法-单词查找树(信息学奥赛一本通-T1337)(包含源程序).rar

    单词查找树,又称为Trie或前缀树,是一种用于存储动态集合或关联数组的高效数据结构。它通过将字符串的关键字映射到树的节点,使得字符串的查找、插入和删除操作能够以接近线性的平均时间复杂度完成。这种数据结构在...

    一个基于trie树的具有联想功能的文本编辑器.zip

    3. **查找操作**:设计一个方法来查找以特定前缀开头的单词,通过遍历Trie树来实现。 4. **删除操作**(可选):如果需要支持删除单词功能,那么需要实现一个删除方法,这通常比插入和查找复杂,因为它需要处理节点...

    TIRE 字典树 论文

    3. **前缀匹配**:Trie树特别适合进行前缀匹配查询,例如查找所有以特定字符串开头的单词。 4. **插入和删除操作**:Trie树的插入和删除操作相对复杂,但仍然比平衡二叉搜索树等其他数据结构更为高效。 在论文...

    Trie树(字典树)的介绍及Java实现

    对于大规模字符串集合,尤其是有大量公共前缀的情况,Trie树的性能优于传统的哈希表或二叉查找树。在内存有限的情况下,Trie树可以有效地压缩存储空间,因为它共享了公共前缀,减少了重复存储。 总结来说,Trie树是...

    字典树查找统计及单词

    在IT领域,字典树(Trie,也称为前缀树或字首树)是一种非常重要的数据结构,常用于高效地存储和检索字符串。在这个场景中,标题“字典树查找统计及单词”指的是利用字典树进行单词查找、统计以及可能的分析操作。...

    php-leetcode题解之实现Trie前缀树.zip

    Trie,也被称为字典树或前缀树,是一种用于存储字符串的数据结构,尤其适合进行高效的字符串查找。它的主要特点是能通过字典序的方式快速地查找具有相同前缀的字符串。Trie树的每个节点通常包含一个字符,并且有指向...

Global site tag (gtag.js) - Google Analytics