找到提供最佳压缩的前缀substring

Question

问题:

给定一个字符串列表,找到子字符串,如果从匹配的所有字符串的开头减去并用转义字节替换,则给出最短的总长度.

例:

"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),这太贵了.

Answer 1

使用前缀树林(trie)......

  f_2    b_1
 /       |
 o_2     a_1
 |       |
 o_2     r_1
 |
 l_1

然后,我们可以通过最大化找到最好的结果,并保证它 (depth * frequency)来被替换为你的转义字符.您可以通过执行分支和边界深度优先搜索来优化搜索.

关于复杂性:O(C),如评论中所提到的,用于构建它,以及寻找最优,它取决于.如果您订购第一个元素频率(O(A) - 其中A是语言字母表的大小),那么您将能够删除更多分支,并且很有可能获得次线性时间.

我认为这很清楚,我不会写出来 - 这是一个家庭作业？;)