1. 题目源地址：http://acm.hdu.edu.cn/showproblem.php?pid=1247
2. 解题思路：
第一次接触字典树，代码也是参考别人的。代码参考博客：http://blog.csdn.net/red_flame/article/details/8449537
3. 解题代码：
//HOJ--1247:Hat’s Words 字典树
#include<iostream>
#include<string.h>
#include<string>
#define M 50005
#define N 60
using namespace std;
char str[M][N];
char s1[N],s2[N];
struct node
{
int flag;
node *next[26];
};
void Insert(node *root,char s[])
{
int i=0,j,k;
int len=strlen(s);
node *current=root;
while(i<len)
{
k=s[i]-'a';
if(current->next[k]==NULL)
{
node *p=new node;
for(j=0;j<26;j++)
p->next[j]=NULL;
p->flag=0;
if(i==len-1)
p->flag=1;
current->next[k]=p;
current=p;
}
else current=current->next[k];
i++;
}
}
bool Find(node *root,char s[])
{
int i=0,j,k;
int len=strlen(s);
node *current=root;
while(i<len)
{
k=s[i]-'a';
if(current->next[k]==NULL)
return false;
current=current->next[k];
i++;
}
return current->flag;
}
int main()
{
int i,j,k;
int m,n,temp,cnt=0;
node *root=new node;
for(i=0;i<26;i++)
root->next[i]=NULL;
root->flag=0;
while(gets(str[cnt]))
{
Insert(root,str[cnt]);
cnt++;
}
for(i=0;i<cnt;i++)
{
temp=strlen(str[i]);
for(j=1;j<temp;j++)
{
memset(s1,0,sizeof(s1));
memset(s2,0,sizeof(s2));
for(m=0;m<j;m++)
s1[m]=str[i][m];
for(n=j;n<temp;n++)
s2[n-j]=str[i][n];
if(Find(root,s1) && Find(root,s2))
{
cout<<str[i]<<endl;
break;
}
}
}
//system("pause");
return 0;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/163010.html
