我敢打赌，以前有人解决过这个问题，但我的搜索却空了。
我想将单词列表打包到缓冲区中，以跟踪每个单词的起始位置和长度。诀窍是我想通过消除冗余来有效地打包缓冲区。
示例：洋娃娃洋娃娃屋
它们可以像一样简单地打包到缓冲区中dollhouse，记住doll从位置0开始是四个字母，在位置0 dollhouse是九个字母，在位置house3是五个字母。
dollhouse
doll
house
到目前为止，我想出的是：
由于长词通常包含较短的词，因此效果很好，但是应该可以做得更好。例如，如果我将单词列表扩展为包括布娃娃，那么我的算法dollhouseragdoll将比效率低ragdollhouse。
dollhouseragdoll
ragdollhouse
这是一个预处理步骤，因此我不必担心速度。O（n ^ 2）可以。另一方面，我的实际列表中有成千上万个单词，因此O（n！）可能不存在。
附带说明一下，此存储方案用于TrueType字体的“名称”表中的数据，参见。http://www.microsoft.com/typography/otspec/name.htm
这是 最短的超 字符串 问题 ：找到包含一组给定字符串作为子字符串的最短字符串。根据这份IEEE论文（不幸的是，您可能无法获得），准确地解决此问题是 NP-complete 。但是，可以使用启发式解决方案。
第一步，您应该找到所有属于其他字符串的子字符串的字符串并将其删除（当然，您仍然需要以某种方式记录它们相对于包含的字符串的位置）。可以使用广义后缀树有效地找到这些完全包含的字符串。
然后，通过重复合并重叠时间最长的两个字符串，可以保证产生一个长度不小于最小可能长度的4倍的解决方案。正如Zifre对KonradRudolph的回答的评论所建议的那样，应该可以通过使用两个基数树快速找到重叠大小。或者，您也许可以以某种方式使用广义后缀树。
抱歉，我无法为您找到一个体面的链接- 似乎没有Wikipedia页面，或有关此特定问题的任何可公开访问的信息。尽管未提供建议的解决方案，但此处已简要提及。
