a ahat hat hatword hziee word
ahat hatword
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAX = 30;
struct trie{
bool point; //单词的结尾标记
trie *next[MAX];
};
trie *root=new trie;
int k=0,slen,k1,k2;
char s1[MAX],s2[MAX];
char str[50005][MAX],s[MAX];
void createTrie(char *s){
trie *p=root, *q;
int len=strlen(s),pos;
for(int i=0;i<len;i++){
pos=s[i]-'a';
if(p->next[pos]==NULL){
q=new trie;
q->point=false;
for(int j=0;j<MAX;j++)
q->next[j]=NULL;
p->next[pos]=q;
p=p->next[pos];
}
else{
p=p->next[pos];
}
}
p->point=true;
}
bool findTrie(char *s){
trie *p=root;
int len=strlen(s),pos;
for(int i=0;i<len;i++){
pos=s[i]-'a';
if(p->next[pos]==NULL)
return false;
p=p->next[pos];
}
return p->point;
}
void delTrie(trie *Root){
for(int i=0;i<MAX;i++){
if(Root->next[i]!=NULL)
delTrie(Root->next[i]);
}
free(Root);
}
int main(){
freopen("liuchu.txt","r",stdin);
for(int i=0;i<MAX;i++)
root->next[i]=NULL;
while(scanf("%s",s)!=EOF){
slen=strlen(s);
for(int i=0;i<slen;i++)
str[k][i]=s[i];
k++;
createTrie(s);
}
for(int i=0;i<k;i++){
slen=strlen(str[i]);
k1=0;
for(int j=0;j<slen-1;j++){
k2=0;
s1[k1++]=str[i][j];
for(int h=j+1;h<slen;h++)
s2[k2++]=str[i][h];
s2[k2]='\0';
if(findTrie(s1)&&findTrie(s2)){
printf("%s\n",str[i]);
break;
}
}
memset(s1,'\0',sizeof(s1));
memset(s2,'\0',sizeof(s2));
}
delTrie(root);
return 0;
}
原文:http://blog.csdn.net/jhgkjhg_ugtdk77/article/details/44628731