Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 字典树水之！！！

Posted by wocha at 2012-07-30 14:16:11 on Problem 2001
```#include <stdio.h>
#include <iostream>
#include <queue>
#include <algorithm>
#include <stack>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#define Size 26
using namespace std;
typedef struct T
{
int num;
T *dic[Size];
};
void init(T *t)
{
for(int i=0;i<Size;i++)
{
t->dic[i]=NULL;
}
t->num=0;
}
void buildtree(T *t,char *in)
{

if(*in)
{
int id=*in-'a';
if(t->dic[id]==NULL)
{
t->dic[id]=new T;
init(t->dic[id]);
}
(t->dic[id]->num)++;
buildtree(t->dic[id],in+1);
}
}
int query(T *t,char *in)
{
int id=*in-'a';
if(t->dic[id]!=NULL)
{
if(*(in+1)=='\0')
{
return t->dic[id]->num;
}
else
{
return query(t->dic[id],in+1);
}
}
else
{
return 0;
}
}
int main()
{
T *s;
s=new T;
init(s);
int i=0;
char str[1050][33];
while(gets(str[i]),str[i][0]!='0')
{
buildtree(s,str[i]);
i++;
}
int h;
for(int j=0;j<i;j++)
{
int len=strlen(str[j]);
printf("%s ",str[j]);
for( h=0;h<len;h++)
{
char s1=str[j][h+1];
str[j][h+1]='\0';
if(query(s,str[j])==1)
{
printf("%s\n",str[j]);

break;
}
else
str[j][h+1]=s1;
}
if(h==len) printf("%s\n",str[j]);
}
return  0;
}
```

Followed by:

User ID:
Title:

Content: