918
poj2001 trie
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int T[100100][26] = {0}, num[100100] = {0}, sz = 0;
char s[1010][21];
void Insert(char *s){
int u = 0;
for (int i = 0; s[i]; i++){
int c = s[i] - 'a';
if (!T[u][c])
T[u][c] = ++sz;
u = T[u][c];
num[u] ++;
}
}
void Search(char *s){
int u = 0;
for (int i = 0; s[i]; i++){
if (num[u] == 1) break;
u = T[u][s[i] - 'a'];
printf("%c", s[i]);
}
printf("\n");
}
int main(){
int n = 0;
while (scanf("%s", s[++n]) == 1)
Insert(s[n]);
for (int i = 1; i <= n; i++){
printf("%s ", s[i]);
Search(s[i]);
}
return 0;
} 最后更新：2017-08-23 00:02:29