字典树模板题目
#include<stdio.h> #include<string.h> #include<stdlib.h> struct tree { struct tree *son[26]; int count; char str[20]; }*root; void insert(char *p,char s[]) { int i,k,j; tree *cur=root,*next; int len=strlen(p); for(i=0;i<len;i++) { k=p[i]-'a'; if(cur->son[k]!=NULL) cur=cur->son[p[i]-'a']; else { next=new(tree); for(j=0;j<26;j++) next->son[j]=NULL; next->count=0; cur->son[p[i]-'a']=next; cur=next; } } cur->count=1; strcpy(cur->str,s); } int find(char *p) { int i; tree *cur=root; int len=strlen(p); for(i=0;i<len;i++) { int k=p[i]-'a'; if(cur->son[k]==NULL) break; else cur=cur->son[k]; } if(i<len||cur->count==0) return 0; else printf("%s\n",cur->str); } int main() { int i,j,k; char s1[20],s2[20],s[100]; root=new(tree); for(i=0;i<26;i++) root->son[i]=NULL; root->count=0; while(gets(s),s[0]) { j=0; for(i=0;s[i]!=' ';i++) s1[j++]=s[i]; s1[j]='\0'; j=0; for(i=i+1;s[i];i++) s2[j++]=s[i]; s2[j]='\0'; insert(s2,s1); } while(scanf("%s",s)!=-1) { j=find(s); if(j==0) printf("eh\n"); } return 0; }