首页 > 代码库 > hdu 1247 Hat’s Words (字典树模板)
hdu 1247 Hat’s Words (字典树模板)
//那个单词是有出现的两个单词构成的 # include <cstdio> # include <cstring> # include <algorithm> # include <iostream> # define MAX 26 using namespace std; typedef struct Trie_Node { bool isWord; struct Trie_Node *next[MAX]; } Trie; char s[50000][50]; void insert(Trie *root,char *word)//生成字典树 { Trie *p=root; while(*word!='\0') { if(p->next[*word-'a']==NULL) { Trie *temp=(Trie*)malloc(sizeof(Trie)); for(int i=0; i<MAX; i++) { temp->next[i]=NULL; } temp->isWord=false; p->next[*word-'a']=temp; } p=p->next[*word-'a']; word++; } p->isWord=true; } bool search(Trie *root,char *word)//查找单词是否存在 { Trie *p=root; for(int i=0; word[i]!='\0'; i++) { if(p==NULL||p->next[word[i]-'a']==NULL) return false; p=p->next[word[i]-'a']; } return p->isWord; } void del(Trie *root)//释放空间 { for(int i=0; i<MAX; i++) { if(root->next[i]!=NULL) { del(root->next[i]); } } free(root);//释放malloc申请的空间 } int main() { int i,j; int count=0; char str[50]; Trie *root=(Trie*)malloc(sizeof(Trie)); for(i=0; i<MAX; i++) { root->next[i]=NULL; } root->isWord=false; while(~scanf("%s",str)) { strcpy(s[count++],str); insert(root,str); } for(i=0; i<count; i++) { for(j=1; j<=strlen(s[i])-1; j++) { char temp1[50]= {'\0'}; char temp2[50]= {'\0'}; strncpy(temp1,s[i],j);//枚举两部分 strncpy(temp2,s[i]+j,strlen(s[i])-j); if(search(root,temp1)&&search(root,temp2)) { printf("%s\n",s[i]); break; } } } del(root); return 0; }
hdu 1247 Hat’s Words (字典树模板)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。