字典树trie

自用笔记算法

字典树

HDU 1251

Problem Description

Input

Output

Sample Input

Sample Output

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<string.h>
#include<iostream>
using namespace std;
typedef struct Trie
{
	int v;
	struct Trie *next[26];
}trie;
trie *root;
trie *newnode()
{
	trie *temp=new trie;
	temp->v=1;
	for(int i=0;i<26;i++)
	   temp->next[i]=NULL;
    return temp;
}
void creattrie(char *str)
{
	int len=strlen(str);
	trie *p=root;
	for(int i=0;i<len;i++)
	{
		int id=str[i]-'a';
		if(p->next[id]==NULL)
		   p->next[id]=newnode();
        else 
			p->next[id]->v++;
        p=p->next[id];
	}
}
int findtrie(char *str)
{
	int len=strlen(str);
	trie *p=root;
	for(int i=0;i<len;i++)
	{
		int id=str[i]-'a';
		p=p->next[id];
		if(p==NULL)
			return 0;
	}
	return p->v;
}
int main()
{
	char str1[15],str2[15];
	root=newnode();
	while(gets(str1)&&str1[0]!='\0')
		creattrie(str1);
	while(cin>>str2)
	{
		int re=findtrie(str2);
		cout<<re<<endl;
	}
	return 0;
}

思路

字典树模版题。

注意事项

根节点root也需要初始化。本题要求读入与查找中需要空行，注意输入格式gets(str1)&&str1[0]!=’\0’。

HDU 1671

Problem Description

Input

Output

Sample Input

Sample Output

题目要求

输入一连串电话号码。求当中有没有一个电话是另一个电话号码的前缀。

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<string.h>
#include<iostream>
#define MAX 9
using namespace std;
typedef struct Trie
{
	bool end;
	struct Trie *next[MAX+1];
}trie;
bool flag;
trie *newnode()
{
	trie *temp=new trie;
	temp->end=false;
	for(int i=0;i<=MAX;i++)
	   temp->next[i]=NULL;
    return temp;
}
void creattrie(char *str,trie *root)
{
	int len=strlen(str);
	trie *p=root;
	for(int i=0;i<len;i++)
	{
		int id=str[i]-'0';
		if(p->next[id]==NULL)
			p->next[id]=newnode();
		if(p->next[id]->end==true)
		{
			flag=true;
			return;
		}
		p=p->next[id];
	}
	p->end=true;
	for(int i=0;i<=MAX;i++)
		if(p->next[i]!=NULL)
		{
			flag=true;
			break;
		}
}
void del(trie *root)
{
    for(int i=0;i<=MAX;i++)
        if(root->next[i]!=NULL)
            del(root->next[i]);
    free(root);
}
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int n;
		cin>>n;
		flag=false;
		trie *root=newnode();
		for(int i=0;i<n;i++)
		{
			char str[11];
			cin>>str;
			if(flag==false)
				creattrie(str,root);
		}
		if(flag==false)
			cout<<"YES"<<endl;
		else
			cout<<"NO"<<endl;
		del(root);
	}
	return 0;
}

思路

与字典树的模版略有不同，区别在于不是找前缀的词频，而是求是否重复出现。需要定义end记录每个电话号码的末尾，flag记录是否重复出现。

注意事项

本题需要free掉存储树的内存空间，不然会超内存。MAX定义为9，所以指针中的next域为MAX+1.

UVa 12333

题目要求
The well-known Fibonacci sequence is defined as following:
F(0) = F(1) = 1
F(n) = F(n − 1) + F(n − 2) ∀n ≥ 2
Here we regard n as the index of the Fibonacci number F(n).
This sequence has been studied since the publication of Fibonacci’s book Liber Abaci. So far, many
properties of this sequence have been introduced.
You had been interested in this sequence, while after reading lots of papers about it. You think
there’s no need to research in it anymore because of the lack of its unrevealed properties. Yesterday,
you decided to study some other sequences like Lucas sequence instead.
Fibonacci came into your dream last night. “Stupid human beings. Lots of important properties
of Fibonacci sequence have not been studied by anyone, for example, from the Fibonacci number
347746739…”
You woke up and couldn’t remember the whole number except the first few digits Fibonacci told
you. You decided to write a program to find this number out in order to continue your research on
Fibonacci sequence.

input
There are multiple test cases. The first line of input contains a single integer T denoting the number
of test cases (T ≤ 50000).
For each test case, there is a single line containing one non-empty string made up of at most 40
digits. And there won’t be any unnecessary leading zeroes.

ouput
For each test case, output the smallest index of the smallest Fibonacci number whose decimal notation
begins with the given digits. If no Fibonacci number with index smaller than 100000 satisfy that
condition, output ‘-1’ instead — you think what Fibonacci wants to told you beyonds your ability.

Sample Input
15
1
12
123
1234
12345
9
98
987
9876
98765
89
32
51075176167176176176
347746739
5610

Sample Output
Case #1: 0
Case #2: 25
Case #3: 226
Case #4: 1628
Case #5: 49516
Case #6: 15
Case #7: 15
Case #8: 15
Case #9: 43764
Case #10: 49750
Case #11: 10
Case #12: 51
Case #13: -1
Case #14: 1233
Case #15: 22374

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<string.h>
#include<iostream>
#define MAX 10
using namespace std;
typedef struct Trie
{
	struct Trie *next[MAX];
	int id;
}trie;
trie *newnode()
{
	trie *temp=new trie;
	temp->id=0;
	for(int i=0;i<MAX;i++)
	   temp->next[i]=NULL;
    return temp;
}
void creattrie(trie *root,char *str,int len,int id)
{
	trie *p=root;
	for(int i=0;i<len;i++)
	{
		int num=str[i]-'0';
		if(p->next[num]==NULL)
			p->next[num]=newnode();
         p=p->next[num];  
		 if(p->id==0)
			 p->id=id;
	}
}
int search(trie *root,char *str)
{
	int len=strlen(str);
	trie *p=root;
	if(*str=='1'&&strlen(str)==1)
		return 0;
	else
	{
		for(int i=0;i<len;i++)
		{
			int num=str[i]-'0';
			p=p->next[num];
			if(p==NULL)
				return -1;
		}
		return p->id;
	}
}
int F[2][21000];
char FF[42],In[42];
int main()
{
	trie *root;
	root=newnode();
	memset(F,0,sizeof(F));
	F[0][0]=F[1][0]=1;
	creattrie(root,"1",1,0);
	int s=0,e=1,r,count,p,q;
	for(int i=2;i<100000;i++)
	{
		p=i%2,q=(i+1)%2;
		for(int j=s;j<e;j++)
			F[p][j]=F[p][j]+F[q][j];
		for(int j=s;j<e;j++)
			if(F[p][j]>=10)
			{
				F[p][j]%=10;
				F[p][j+1]+=1;
			}
		if(F[p][e]!=0)
			e++;
		if(e-s>40)
			s++;
		r=e-1,count=0;
		while(r>=0&&count<40)
			FF[count++]=F[p][r--]+'0';
		creattrie(root,FF,count,i);
	}
	int T;
	while(scanf("%d",&T) != EOF)
	{
		for(int i=1;i<=T;i++)
		{
			scanf("%s",In); 
			printf("Case #%d: %d\n",i,search(root,In));  
		}
	}
	return 0;
}

思路

本题是有关斐波拉契数列的前缀问题。运用大数的存储原理才计算菲波拉契数，并且利用滚动数组的原理才减少开销，存储前10w个菲波拉契数的前40位。在构造字典树的同
时记录下每个菲波拉契数的id。最后只要查找前缀最后一个数对应的id即可。

注意事项

查找1的菲波拉契数需要额外考虑，因为它本身的id就为0，所以在菲波拉契数13存入的时候id就会被改动为6，额外考虑。字符型-‘0’=整形。整形+’0’=字符型。滚动数组的
构造方式也需要记忆。

本文标题:字典树trie

文章作者:Hippopmonkey

发布时间:2016-10-31, 20:19:03

最后更新:2017-08-17, 23:18:51

原始链接:http://xuboming8.github.io/2016/10/31/字典树trie/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 字典树
    1. 1.1. HDU 1251
      1. 1.1.1. 参考AC代码
      2. 1.1.2. 思路
      3. 1.1.3. 注意事项
    2. 1.2. HDU 1671
      1. 1.2.1. 题目要求
      2. 1.2.2. 参考AC代码
      3. 1.2.3. 思路
      4. 1.2.4. 注意事项
    3. 1.3. UVa 12333
      1. 1.3.1. 参考AC代码
      2. 1.3.2. 思路
      3. 1.3.3. 注意事项
|