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 1200017623 at 2013-01-10 00:01:23 on Problem 2001
```看Discuss区里的哥们儿都在说字典树，Tries树什么的，把学概B的兄弟吓得够呛。其实这道题大可不必如此费事，简单的比较就能搞定。给初学C++的兄弟们提供个思路：

Source: < C++ Memory: 240K Time: 0ms>

#include<iostream>
#include<cstring>
#include<algorithm>      //排序提速用的，为了0ms不惜一切代价
using namespace std;
const int MAX = 1001;    //要稍微开大一点，防止输入数据中有空行
struct Prefix{
char ch[24];     //字串，24个长度，也是适当的冗余
int PrefixPosition;      //最短前缀位置
}str[MAX];

Prefix* pointer[MAX] = {NULL};    //用指针数组操作，排序时只交换指针
//不影响原来的字符串先后顺序

bool cmp(Prefix*a,Prefix*b){      //要返回bool类型，int不行
return strcmp(a->ch,b->ch) < 0;
}

int main(){

int count = 0,pos1 = 0,pos2 = 0;
while(cin>>str[count].ch){
pointer[count] = &str[count];
++count;
}
//sort the strings pointer in alphabetical order

sort(pointer,pointer+count,cmp);

//Compare
for(int i = 0;i < count;++i){
//和前后比较
if(i > 0)pos1 = pos2;     //这样可减少一半的重复
pos2 = 0;
if(i < count - 1)while(pointer[i]->ch[pos2] && pointer[i]->ch[pos2] == pointer[i+1]->ch[pos2])++pos2;

//用最大的
pointer[i]->PrefixPosition = max(pos1,pos2);
}

for(int i = 0;i < count;++i){
printf("%s ",str[i].ch);
for(int j = 0;j <= str[i].PrefixPosition;++j)

//不要把'\0'打进去
if(str[i].ch[j])putchar(str[i].ch[j]);
printf("\n");
}
return 0;
}
```

Followed by: