当前位置: 代码迷 >> 综合 >> 字典树(tire tree,例题:HDU1247,HDU1251,HDU4825)
  详细解决方案

字典树(tire tree,例题:HDU1247,HDU1251,HDU4825)

热度:56   发布时间:2023-12-06 14:17:58.0

字典树(tire tree):把字母存在树中,其中一条子链(从根节点开始)就是一个单词。

 

核心代码(主要三部分:结构体,插入,查询):

1.创建结构体

struct node
{//isEnd是否是最后一字母//也可以是别的,比较灵活int isEnd;//此处为26个字母(如果更多的话可以增加)struct node *next[26];//构造函数,用于初始化node(){isEnd=0;memset(next,NULL,sizeof(next));}
//直接创建一个头结点
}*root;

2.插入单词

void insert(char *s)
{node *p=root;//遍历字母while (*s!='\0'){//把字母转换成对应数字int d=*s-'a';//看当前节点是否存在if (p->next[d]==NULL){//不存在就new一个p->next[d]=new node();p=p->next[d];}elsep=p->next[d];s++;}//标记p->isEnd=1;return;
}

3.查询函数

int find(char *s)
{node *p=root;while(*s!='\0'){int d=*s-'a';p=p->next[d];if (p!=NULL){//字符串遍历完并且存在到此结束的单词if (*(s+1)=='\0'&&p->isEnd==1)return 1;s++;}elsereturn 0;}return 0;
}

 

例题1:

Hat’s Words(HDU1247)

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

 

Problem Description

A hat’s word is a word in the dictionary that is the concatenation of exactly two other words in the dictionary.
You are to find all the hat’s words in a dictionary.

 

Input

Standard input consists of a number of lowercase words, one per line, in alphabetical order. There will be no more than 50,000 words.
Only one case.

 

Output

Your output should contain all the hat’s words, one per line, in alphabetical order.

 

Sample Input

a

ahat

hat

hatword

hziee

word

 

Sample Output

ahat

hatword

 

Source

HDU1247

题意:给你一组单词,问你有多少个帽子数(自己在单词组中,并且加起来等于自己的两个子串也在单词组中)。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
using namespace std;struct node
{//是否是最后一个字母 int isEnd;struct node *next[26];//构造函数 node(){isEnd=0;memset(next,NULL,sizeof(next));}
}*root;char str[50005][20];
int s=0;void insert(char *s)
{node *p=root;while (*s!='\0'){int d=*s-'a';if (p->next[d]==NULL){p->next[d]=new node();p=p->next[d];}elsep=p->next[d];s++;}p->isEnd=1;return;
}int find(char *s)
{node *p=root;while(*s!='\0'){int d=*s-'a';p=p->next[d];if (p!=NULL){if (p->isEnd==1&&*(s+1)=='\0')return 1;s++;}elsereturn 0;}return 0;
}int find_pre(char *s) 
{node *p=root;while(*s!='\0'){int d=*s-'a';p=p->next[d];if (p!=NULL){if (p->isEnd==1&&find(s+1))return 1;s++;}elsereturn 0;}return 0;
}int main()
{root=new node();while(~scanf("%s",str[s]))insert(str[s++]);for (int i=0;i<s;i++){if (find_pre(str[i]))cout << str[i] << endl;}return 0;
}

 

例题2:

统计难题(HDU1251)

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

 

Problem Description

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

 

Input

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

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

 

Output

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

 

Sample Input

banana

band

bee

absolute

acm

注意:此处为空行

ba

b

band

abc

 

Sample Output

2

3

1

0

 

Source

HDU1251

题意:中文题面很好理解

其实吧这个题目可以用map做

map做法:

#include <cstdio>
#include <iostream>
#include <map>
#include <string>
using namespace std;string s;
map<string,int> m;int main()
{while(getline(cin,s,'\n')&&s.size()!=0){for (int i=1;i<=s.length();i++){string sub=s.substr(0,i);//cout << sub << endl;if (!m.count(sub))m[sub]=1;elsem[sub]++;}}while(cin >> s){cout << m[s] << endl;}return 0;
}

字典树写法: 

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;struct node
{int isEnd,vis;struct node *next[26];node(){isEnd=0;vis=0;memset(next,NULL,sizeof(next));}
}*root;void insert(char *s)
{node *p=root;while (*s!='\0'){int d=*s-'a';if (p->next[d]==NULL){p->next[d]=new node();p=p->next[d];}elsep=p->next[d];p->vis++;s++;}p->isEnd=1;return;
}int find(char *s)
{node *p=root;while(*s!='\0'){int d=*s-'a';p=p->next[d];if (p!=NULL){if (*(s+1)=='\0')return p->vis;s++;}elsereturn 0;}return 0;
}char str[20];int main()
{root=new node();//注意一下获取空行的写法while(gets(str)&&str[0]!='\0'){insert(str);}while(gets(str)){cout << find(str) << endl;}	return 0;
}

 

例题3:

Xor Sum(HDU4825)

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 132768/132768 K (Java/Others)
Total Submission(s): 5169    Accepted Submission(s): 2247

 

Problem Description

Zeus 和 Prometheus 做了一个游戏,Prometheus 给 Zeus 一个集合,集合中包含了N个正整数,随后 Prometheus 将向 Zeus 发起M次询问,每次询问中包含一个正整数 S ,之后 Zeus 需要在集合当中找出一个正整数 K ,使得 K 与 S 的异或结果最大。Prometheus 为了让 Zeus 看到人类的伟大,随即同意 Zeus 可以向人类求助。你能证明人类的智慧么?

 

Input

输入包含若干组测试数据,每组测试数据包含若干行。
输入的第一行是一个整数T(T < 10),表示共有T组数据。
每组数据的第一行输入两个正整数N,M(<1=N,M<=100000),接下来一行,包含N个正整数,代表 Zeus 的获得的集合,之后M行,每行一个正整数S,代表 Prometheus 询问的正整数。所有正整数均不超过2^32。

 

Output

对于每组数据,首先需要输出单独一行”Case #?:”,其中问号处应填入当前的数据组数,组数从1开始计算。
对于每个询问,输出一个正整数K,使得K与S异或值最大。

 

Sample Input

2

3 2

3 4 5

1

5

4 1

4 6 5 6

3

 

Sample Output

Case #1: 4

3

Case #2: 4

 

Source

HDU4825

题意:这个其实就是一个0,1字典树,要使异或最大,在找的时候可以找和所给数字不同的往下找,如果不存在就只能令他一样。

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;int t,n,m,cnt=0,x;struct node
{int num;struct node *next[2];node(){num=0;memset(next,NULL,sizeof(next));}
}*root;void insert(int x)
{bool a[32];int xx=x;node *p=root;for (int i=0;i<32;i++){a[i]=x&1;x>>=1;}for (int i=31;i>=0;i--){if (p->next[a[i]]==NULL){p->next[a[i]]=new node();p=p->next[a[i]];}elsep=p->next[a[i]];}p->num=xx;return;
}int find(int x)
{bool a[32];node *p=root;for (int i=0;i<32;i++){a[i]=x&1;x>>=1;}for (int i=31;i>=0;i--){if (p->next[!a[i]]!=NULL)p=p->next[!a[i]];else p=p->next[a[i]];}return p->num;
}void del(node *p)
{for(int i=0;i<2;i++)if(p->next[i]!=NULL)del(p->next[i]);delete(p);
}int main()
{cin >> t;while(t--){cin >> n >> m;root=new node;for (int i=0;i<n;i++){scanf("%d",&x);insert(x);}printf("Case #%d:\n",++cnt);for (int i=0;i<m;i++){scanf("%d",&x);printf("%d\n",find(x));}del(root);}return 0;
}

 

  相关解决方案