问题：

给定一个字符串列表，请找到子字符串，如果从与之匹配的所有字符串的开头减去该字符串，然后将其替换为转义字节，则该子字符串的总长度最短。

例子：

" 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是语言字母的大小)，那么我们将能够切出更多的分支，并有很大的机会获得次线性时间。

我认为这是明确的，我不打算把它写起来 - 什么，这是一个家庭作业？ ;)

好吧，第一步将是对列表进行排序。然后遍历该列表，将每个元素与前一个元素进行比较，并跟踪最长的2个字符，3个字符，4个字符等。然后数字是20个3个字符的前缀好于15个4个字符的前缀。