Shortest Prefixes
题目背景
POJ 2001
题目描述
给出 $n$ 个单词（$1 \leq n \leq 1000$），求出每个单词的非公共前缀，如果没有，则输出自己。
输入格式
输入 N 个单词，每行一个，每个单词都是由 1～20 个小写字母构成。
输出格式
输出 N 行，每行由一个空格的两部分，第一部分是输入的单词，第二部分是该单词在所有单词中的非公共前缀，如果没有，则输出自己。
样例数据 1
输入
1
2
3
4
5
6
7
8
9
10
11
12
| carbohydrate
cart
carburetor
caramel
caribou
carbonic
cartilage
carbon
carriage
carton
car
carbonate
|
输出
1
2
3
4
5
6
7
8
9
10
11
12
| carbohydrate carboh
cart cart
carburetor carbu
caramel cara
caribou cari
carbonic carboni
cartilage carti
carbon carbon
carriage carr
carton carto
car car
carbonate carbona
|
C++代码
典型的trie树的运用,注意删除的问题,否则可能MLE
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
| #include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#define MIN 30
#define MAX 1100
using namespace std;
struct node {
int count;
node *next[MIN];
} * root;
char str[MAX][MIN];
node *CreateNode() {
node *p;
p = (node *)malloc(sizeof(node));
p->count = 1;
for (int i = 0; i < 26; ++i) p->next[i] = NULL;
return p;
}
void release(node *p) {
for (int i = 0; i < 26; ++i)
if (p->next[i] != NULL) release(p->next[i]);
free(p);
}
void insert(char *str) {
int i = 0, k;
node *p = root;
while (str[i]) {
k = str[i++] - 'a';
if (p->next[k] == NULL)
p->next[k] = CreateNode();
else
p->next[k]->count++;
p = p->next[k];
}
}
void search(char *str) {
int i = 0, k, j;
bool flag = false;
node *p = root;
while (str[i] && !flag) {
k = str[i++] - 'a';
p = p->next[k];
if (p->count == 1) {
flag = true;
cout << str << " ";
for (j = 0; j < i; ++j) cout << str[j];
cout << "\n";
}
}
if (!flag) cout << str << " " << str << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
root = CreateNode();
int i;
for (i = 0; cin >> str[i]; ++i) insert(str[i]);
for (int j = 0; j < i; ++j) search(str[j]);
release(root);
}
|
