合并未知字符串的匹配片

Question

我正在解析一个谜题，我有几片大的数字字符串。最初它们似乎是随机的，但是通过一些频率分析，我了解到它们都是大字符串的一部分。

问题是这些切片可能包含大字符串的单独部分，但不包含有关它们所在位置的信息，甚至可能包含单独的子字符串。例如：

text: 0102030405060708091011121314151617181920
slice 1: 010203041516171819
slice 2: 030405060717181920
slice 3: 060708091011121314
slice 4: 040506071213141516

注意通过滑动切片如何重建原始文本：

slice 1: 01020304                    1516171819
slice 2:     0304050607                  17181920
slice 3:           060708091011121314
slice 4:       04050607        1213141516

由于原始文本可能是几百个甚至几千个数字，因此手动进行非常困难且耗时。我有80个切片的集合，它们应该产生一个合并的字符串，这是我没有的原始文本。

我搜索了一些字符串匹配算法，例如最长的公共子字符串，但是它们不包括拆分切片以尝试匹配。同样，diff算法通常不支持一次合并多个字符串，并且两个切片的共同点太少，因此无法使用，通常会给出错误的匹配，否则会失败。

Answer 1

如果我享有声誉，我会发表评论，但是这个问题看起来类似于从大量的小型测序片段组装基因组。不知道最新的技术是什么，但是De Brujin的图表是如何教会我这样做的。

这个问题（关于基因组组装-但同样适用）可能会有所帮助：http://rosalind.info/problems/grep/

以及Rosalind关于De Brujin图的问题的子集http://rosalind.info/search/?q=%20bruijn

Answer 2

• 一次从text中获取两个字符
  • 查看每个切片中是否有切片
• 一次从text中获取三个字符
  • 查看每个切片中是否有切片
• ......
• 一次获取text len(text) - 2中的字符
  • 查看每个切片中是否有切片

在每个步骤中，如果发现序列，则将其从切片中删除。根据您的需求，也许可以颠倒顺序并从最长的顺序开始。如果您可以推断出可以分割多少切片的限制，请使用该限制。

如果切片的长度相对于text的长度为Small，则可以从切片中取出一部分并在text中进行搜索