HDU1247(经典字典树)
2024-08-29 06:25:34
Hat’s Words
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 11894 Accepted Submission(s): 4239
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.
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.
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
题意:‘帽子’单词:由其他两个单词拼接而成。输出所有的帽子单词。字典树。
静态建树:
#include"cstdio"
#include"cstring"
using namespace std;
const int MAXN=;
const int N=;
struct node{
bool val;
node* next[N];
};
node* root;
node memory[MAXN];
int ant; node* create()
{
node* p=&memory[ant++];
for(int i=;i<N;i++)
{
p->next[i]=NULL;
p->val=false;
}
return p;
} void insert(char *s)
{
node* p=root;
for(int i=;s[i];i++)
{
int k=s[i]-'a';
if(p->next[k]==NULL) p->next[k]=create();
p=p->next[k];
}
p->val=true;//若能走到最末端,则返回true;
} bool search(char *s)
{
node* p=root;
for(int i=;s[i];i++)
{
int k=s[i]-'a';
if(p->next[k]==NULL) return false;
p=p->next[k];
}
return p->val;//若只是某个已插入单词的前缀,则返回false;
} int main()
{
int cnt=;
root=create();
char word[MAXN][];
while(scanf("%s",word[cnt])!=EOF)
{
//if(word[cnt][0]=='0') break;
insert(word[cnt]);
cnt++;
}
for(int i=;i<cnt;i++)
{
for(int j=;word[i][j];j++)
{
char fr[]={'\0'};
char re[]={'\0'};
strncpy(fr,word[i],j);
strncpy(re,word[i]+j,strlen(word[i])-j);
if(search(fr)&&search(re))
{
printf("%s\n",word[i]);
break;
}
}
} return ;
}
动态建树:
#include"cstdio"
#include"cstring"
#include"cstdlib"
using namespace std;
const int MAXN=;
const int N=;
struct Node{
bool x;
Node* next[N];
Node()
{
x=false;
for(int i=;i<N;i++) next[i]=NULL;
}
};
char word[MAXN][];
int cnt;
Node *root;
void Insert(char s[])
{
Node *p=root;
for(int i=;s[i];i++)
{
int k=s[i]-'a';
if(p->next[k]==NULL) p->next[k]=new Node();
p=p->next[k];
}
p->x=true;
}
bool Search(char s[])
{
Node *p=root;
for(int i=;s[i];i++)
{
int k=s[i]-'a';
if(p->next[k]==NULL) return false;
p=p->next[k];
}
return p->x;
}
void Del(Node *p)
{
for(int i=;i<N;i++)
{
if(p->next[i]!=NULL)
{
Del(p->next[i]);
}
}
delete p;
}
int main()
{
root=new Node();
while(scanf("%s",word[cnt])!=EOF)
{
//if(word[cnt][0]=='0') break;
Insert(word[cnt]);
cnt++;
}
for(int i=;i<cnt;i++)
{
for(int j=;word[i][j+];j++)
{
char fr[]={'\0'};
char re[]={'\0'};
strncpy(fr,word[i],j);
strncpy(re,word[i]+j,strlen(word[i])-j);
if(Search(fr)&&Search(re))
{
printf("%s\n",word[i]);
break;
}
}
}
Del(root);
return ;
}
最新文章
- mysql 三个表连接查询
- python with as用法
- JavaScript中的作用域链原理
- js选项卡切换效果
- JPA 系列教程11-复合主键-2个@Id
- listbox控件使用
- js中的稀疏数组和密集数组
- BZOJ 1226: [SDOI2009]学校食堂Dining [DP 状压]
- mysql 使用问题?
- C# 操作PDF 图层(Layer)——添加、删除图层、设置图层可见性
- 解决持久化数据太大,单个节点的硬盘无法存储的问题;解决运算量太大,单个节点的内存、CPU无法处理的问题
- 从锅炉工到AI专家(9)
- 输入输出流ObjectInputStream、ObjectOutputStream(对象序列化与反序列化)
- 动态规划-数位DPwindy
- C#绘图:带背景,拖鼠标画矩形和直线
- 移动 web 适配
- controller修改response返回值
- linux ssh远程免密码登入
- R语言 让纵坐标的标签显示为横向
- 自己动手实现一个WEB服务器