trie树水题
#include <iostream> using namespace std; typedef struct node { char data; int count; node * next[26]; node * parent; node() { count=0; memset(next,0,sizeof(next)); } }trie; trie * r; void insert(char * s)//把单词插入trie树中 { if(r==NULL) r=new trie; trie * p=r; int di; while(*s!='\0') { di=*s-'a'; if(p->next[di]==NULL) { p->next[di]=new trie; p->next[di]->data=*s; } p->next[di]->count++;//记录树中每个节点被几个单词所覆盖 p=p->next[di]; s++; } } void find(char * s) { trie * tem=r; while(*s!='\0') { int di=*s-'a'; cout<<tem->next[di]->data; if(tem->next[di]->count==1) break; tem=tem->next[di]; s++; } } int main() { char s[1010][25]; r=NULL; int tot=0; while(cin>>s[tot]) { insert(s[tot]); tot++; } int i; for(i=0;i<tot;i++) { cout<<s[i]<<" "; find(s[i]); cout<<endl; } return 0; }