POJ2001《Shortest Prefixes》

一月 18, 2020 4580

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

传送门：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
11
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
6
例如“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
91
#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;
}