传送门:http://poj.org/problem?id=2001
解题思路:
简单的字典树
实现代码:
#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <string> using namespace std; const int N=27; struct node{ int cnt; node *childs[N]; node(){ cnt=0; for(int i=0;i<N;i++) childs[i]=NULL; } }; node *root=new node; node *current,*newnode; void insert(char *str){ int n=strlen(str); current=root; for(int i=0;i<n;i++){ int m=str[i]-'a'; if(current->childs[m]!=NULL){ current=current->childs[m]; (current->cnt)++; }else{ newnode=new node; (newnode->cnt)++; current->childs[m]=newnode; current=newnode; } } } void search(char *str){ int n=strlen(str); current=root; for(int i=0;i<n;i++){ int m=str[i]-'a'; if(current->cnt==1){ printf(" "); return; }else{ printf("%c",str[i]); } current=current->childs[m]; } printf(" "); } int main(){ char a[5000][300]; int n=0; while(scanf("%s",a[n])!=EOF){ insert(a[n]); n++; } for(int i=0;i<n;i++){ printf("%s ",a[i]); search(a[i]); } }