poj2001 Shortest Prefixes

poj2001 Shortest Prefixes

題意：給你一些字符串 對於每個字符串 求出它們特有的最小前綴 輸出格式 字符串 + 最小前綴

思路：字典樹；

代碼：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#define INF 1000000000000
#define N 1010
#define LL long long
#define eps 10E-9
#define mem(a) memset(a,0,sizeof(a))
#define w(a) while(a)
#define s(a) scanf("%d",&a)
#define ss(a,b) scanf("%d%d",&a,&b)
#define sss(a,b,c) scanf("%d%d%d",&a,&b,&c)
using namespace std;
char str[N][25];
struct node
{
int sum;
struct node *next[26];
node ()//構造函數 初始化用
{
sum=0;
mem(next);
}
} ;
node *root=NULL;
void maketree(char *s)
{
node *p=root;
node *tmp=NULL;
for(int i=0; i {
if(p->next[s[i]-'a']==NULL)
{
tmp=new node ;
p->next[s[i]-'a']=tmp;
}
p=p->next[s[i]-'a'];
p->sum++;
}
}
void searchtree(char *s)
{
node *p=root;
for(int i=0; i {
p=p->next[s[i]-'a'];
printf("%c",s[i]);
//cout< if(p->sum==1)
break;
}
}
int main()
{
int j,i;
int num=0;
root =new node;
while(cin>>str[num])
{
maketree(str[num]);
num++;
}
for(int i=0; i {
printf("%s ",str[i]);
searchtree(str[i]);
cout< }
return 0;
}