我想将一个单词列表打包到一个缓冲区中,跟踪每个单词的起始位置和长度.诀窍是我想通过消除冗余来有效地打包缓冲区.
示例：娃娃娃娃屋
这些可以简单地作为玩具屋打包到缓冲区中,记住玩偶是从位置0开始的四个字母,玩偶屋是0处的九个字母,而房子是3处的五个字母.
到目前为止我想出的是：
>将最长的单词排序为最短的:(娃娃屋,房子,洋娃娃)
>扫描缓冲区以查看字符串是否已作为子字符串存在,如果是,请记下该位置.
>如果它尚不存在,请将其添加到缓冲区的末尾.
由于长词通常包含较短的单词,因此效果很好,但应该可以做得更好.例如,如果我将单词列表扩展为包含ragdoll,那么我的算法会出现娃娃屋,它比ragdollhouse效率低.
这是一个预处理步骤,所以我对速度并不十分担心. O(n ^ 2)很好.另一方面,我的实际列表有数万个单词,所以O(n！)可能是不可能的.
作为旁注,这个存储方案用于TrueType字体的`name’表中的数据,参见. http://www.microsoft.com/typography/otspec/name.htm
解决方法
作为第一步,您应该找到所有字符串作为其他字符串的子字符串并删除它们(当然您仍然需要以某种方式记录它们相对于包含字符串的位置).使用generalised suffix tree可以有效地找到这些完全包含的字符串.
然后,通过重复合并具有最长重叠的两个字符串,可以保证生成长度不小于最小可能长度的4倍的解.应该可以通过使用两个基数树来快速找到重叠大小,如Zifre在Konrad Rudolph’s answer的评论所建议的那样.或者,您可能能够以某种方式使用广义后缀树.
对不起,我无法为您找到一个不错的链接 – 似乎没有维基百科页面,或任何有关此特定问题的公开信息.尽管没有提供建议的解决方案,但是简要地提到了here.
