问题:
给定一个字符串列表，找到一个子字符串，如果从匹配的所有字符串的开头减去并用转义字节替换，则给出最短的总长度。
示例:
“foo”，“fool”，“bar”
结果是:“foo”作为基本字符串，字符串 “\0”、“\0l”、“bar” 总长度为 9 个字节。 "\0" 是转义字节。原始字符串的长度之和为10，所以在这种情况下我们只保存了一个字节。
一个朴素的算法看起来像:
for string in list
for i = 1, i < length of string
calculate total length based on prefix of string[0..i]
if better than last best, save it
return the best prefix
这会给我们答案，但它有点像 O((n*m)^2)，这太昂贵了。
最佳答案
使用前缀树森林 (trie)...
f_2 b_1
/ |
o_2 a_1
| |
o_2 r_1
|
l_1
然后，我们可以找到最好的结果，并通过最大化 (depth * frequency) 来保证它，这将被你的转义字符替换。您可以通过分支定界深度优先搜索最大值来优化搜索。
关于复杂性:O(C)，如评论中所述，用于构建它和寻找最优值，这取决于。如果您对第一个元素的频率进行排序(O(A)——其中 A 是语言字母表的大小)，那么您将能够切出更多的分支，并且很有可能获得亚线性时间。
我想这很清楚，我不会写出来——这是什么家庭作业？ ;)
关于algorithm - 找到提供最佳压缩的前缀子串，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/150690/