POJ2001《Shortest Prefixes》

这题在纸上手玩一遍找找规律就出来了

传送门:http://poj.org/problem…

解析

首先看到这是个字符串题

再然后一想,这个要处理前缀相等问题

好,就是你了,Trie


先把给定的字符串插进 Trie 里

在纸上画出样例的 Trie 树,手玩一下,找找规律

应该可以发现这样一句废话:
一个字符串的「最短无歧义缩写」是该字符串到「它的『最长有歧义缩写』的最后一位」的下一位所构成的前缀

举个例子:

1
2
3
4
5
6
字符串“wyhaksx”和“wyhaknoi”
w y h a k s x
w y h a k n o i
此时 wyhak 这个缩写是有歧义的,因为它两句话都能表示,而且它还是最长有歧义缩写;
但是再加一个字母,wyhaks 就没有歧义了,是最短无歧义缩写,
因为它只能表示 wyhaksx 不能表示 wyhaknoi,而你找不到比它更短的了

同时对照着 Trie 树看看(再添加一个“wyhac”加强例子的一般性):

1
2
3
4
5
6
7
8
9
10
w → y → h↘
a → c

k
↙ ↘
s n
↓ ↓
x o

i

你发现了什么?
最长有歧义缩写的结尾正好在深度最大的分支处!
最短无歧义缩写的结尾正好是深度最大的分支的子节点!

两个字符串,一个字符串是另一个字符串的子串(“wyh”和“wyhak”)这种情况先不考虑。


那么现在问题转化成了如何找深度最高的分支的位置。

这个比较简单,在插入字符串的时候,对于每一个节点,记一下这个点有几条向下连的边,连边数超过 2 的话就是分支;再记一下这个节点的父亲是谁;插完之后记一下这个字符串对应结尾在 Trie 中的位置(也就是动态开点后的节点编号)。

查找的时候,从刚刚记的结尾位置开始向上查找,直到找到第一个分支,返回它的子节点编号即可

代码:

1
2
3
4
5
6
7
8
9
10
11
12
int findNode(int down) {
// 沿着叶子节点往上走,找到第一个分叉节点,返回它的儿子
// 分叉节点即为向下连的边超过两条的点
int now = location[down]; // 获取这个字符串对应的结尾节点
while (true) {
if (now == 1) break; // 居然滚回根节点了
int father = node[now].from; // 父亲节点
if (node[father].edges >= 2) break; // 找到了 orz
now = father; // 往上跳
}
return now;
}

接下来只需要顺着下去溜一遍,把字符串复制一下输出就好了,需要注意的是到了刚刚找到的节点要 break

代码:

1
2
3
4
5
6
7
8
9
10
11
std::string find(int down) {
int endNode = findNode(down); // 调用上面的函数获取最终节点
std::string res = ""; std::string &ds = originalStrings[down];
int now = 1;
for (int i = 0, len = (int) ds.length(); i < len; ++i) {
int next = node[now].next[toNum(ds[i])]; // 获取当前节点的子节点
res += ds[i]; now = next; // 复制字符串,更新位置
if (next == endNode) break; // 如果下一个节点是终点,那就停掉
}
return res; // 返回这个输出的结果就好了
}

One more thing.

「两个字符串,一个字符串是另一个字符串的子串的情况」?
答案:简单粗暴地在字符串尾加一个特殊字符,强行搞出一个分支来

1
2
3
4
5
例如“wyh”和“wyhak”
可以修改成“wyh#”和“wyhak#”

w → y → h → #
↘ a → k → #

这样不就有分支了吗

那是不是还要修改一下 std::string find(int) 函数?
不用!

注意到这种情况下,调用 findNode(int) 函数获得的实际上是 # 所在的节点编号,而 find(int) 函数在找的时候,循环 至多 会循环到 原字符串的长度,复制字符串 至多 会复制 完整的原字符串,所以压根不需要特判。

代码实现

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>

const int MAXSTRS = 1000 + 10;

std::string originalStrings[MAXSTRS];
int location[MAXSTRS];

class Trie {
private:
static const int MAXNODES = 30000 + 10;

struct Node {
bool str; int from, siz, edges;
int next[30];
Node() {
str = 0; from = siz = edges = 0;
memset(next, 0, sizeof next);
}
};
Node node[MAXNODES];
int cnt;

int toNum(const char &s) {
if (s == '#') return 27;
return s - 'a' + 1;
}

public:
Trie() { cnt = 1; }

void insert(std::string s, int down) {
int now = 1, strLen = (int) s.length();
for (int i = 0; i < strLen; ++i) {
int &next = node[now].next[toNum(s[i])];
if (next == 0) {
next = ++cnt; node[next].from = now;
++node[now].edges;
}
now = next;
}
node[now].str = true;
location[down] = now;
}
int findNode(int down) {
// 沿着叶子节点往上走,找到第一个分叉节点,返回它的儿子
// 分叉节点即为向下连的边超过两条的点
int now = location[down];
while (true) {
if (now == 1) break; // md 居然滚回根节点了
int father = node[now].from; // 父亲节点
// printf("\tNow on node [%d], its father is [%d], \n\tits father's out-edges amount is %d;\n", now, father, node[father].edges);
if (node[father].edges >= 2) break; // 找到了 orz
now = father; // 往上跳
}
return now;
}
std::string find(int down) {
// 获得答案
// printf("[DEBUG] Now processing [%d] -> %s:\n", down, originalStrings[down].c_str());
int endNode = findNode(down);
// printf("\tendNode = %d\n", endNode);
// printf("\tCopying string...\n");
std::string res = ""; std::string &ds = originalStrings[down];
int now = 1;
for (int i = 0, len = (int) ds.length(); i < len; ++i) {
int next = node[now].next[toNum(ds[i])];
// printf("\tnow = %d, next = %d, now char = %c\n", now, next, ds[i]);
res += ds[i]; now = next;
if (next == endNode) break;
}
return res;
}
} trie;

int main() {
int n = 0;
while (std::cin >> originalStrings[++n]);
--n;
for (int i = 1; i <= n; ++i)
trie.insert(originalStrings[i] + "#", i);
// trie.initSize();
for (int i = 1; i <= n; ++i) {
printf("%s %s\n", originalStrings[i].c_str(), trie.find(i).c_str());
}
return 0;
}