| ||||||||||
Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
第一题字典树AC了,留贴纪念一下(附代码)#include<algorithm> #include<iostream> using namespace std; #define MAX 1100 char str[MAX][25]; const int sonnum=26,base='a'; struct Trie { int num;//to remember how many words can reach here bool terminal;//if terminal==true ,the current point has no following point struct Trie *son[sonnum]; }; Trie *NewTrie()//create a new node { Trie *temp=new Trie; temp->num=1;temp->terminal=false; for(int i=0;i<sonnum;i++) temp->son[i]=NULL; return temp; } void Insert(Trie *pnt,char *s,int len) { Trie *temp=pnt; for(int i=0;i<len;i++) { if(temp->son[s[i]-base]==NULL) temp->son[s[i]-base]=NewTrie(); else temp->son[s[i]-base]->num++; temp=temp->son[s[i]-base]; } temp->terminal=true; } void Delete(Trie *pnt)//delete the whole tree; { if(pnt!=NULL) { for(int i=0;i<sonnum;i++) if(pnt->son[i]!=NULL) Delete(pnt->son[i]); delete pnt; pnt=NULL; } } Trie*Find(Trie *pnt,char *s,int len) { Trie *temp=pnt; for(int i=0;i<len;i++) { if(temp->son[s[i]-base]!=NULL) {printf("%c",s[i]);temp=temp->son[s[i]-base];if(temp->num==1) break;} else return NULL; } return temp; } void solve(Trie *pnt,int num) { for(int i=0;i<num;i++) { printf("%s ",str[i]); int len=strlen(str[i]); Find(pnt,str[i],len); printf("\n"); } } int main() { int num=0; int len; Trie *pnt; pnt=NewTrie(); while(scanf("%s",str[num])!=EOF) { len=strlen(str[num]); Insert(pnt,str[num],len); num++; } solve(pnt,num); Delete(pnt); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator