从字符串中查找子字符串

Question

输入:字符串S = AAGATATGATAGGAT.

输出:最大重复次数,如GATA(如位置3和8),GAT(如位置3,8和13)等等......

• 最大重复是子串t在S中发生k> 1次,并且如果t向左或向右延伸,则它将发生少于k次.

• 内部节点的叶子后代是后缀,每个后缀都有一个左侧字符.

• 如果所有叶子后代的左侧字符都不完全相同,则称为"左侧多样化"节点.

• 最大重复是左 - 多样的内部节点.

总体思路:

• 构建后缀树,然后在树上执行DFS(深度优先搜索)

• 对于每个叶子,用左侧字符标记它

• 对于每个内部节点:

• 如果至少有一个孩子标有*,则用*标记*

• 否则,如果其子标签不同,请标注*.

• 否则,所有孩子都有相同的标签,将其复制到当前节点

上述想法是否正确？伪代码怎么样？然后我可以尝试自己编写程序.

Answer 1

你的想法很好，但是使用后缀树你可以做一些更容易的事情。

令 T 为序列的后缀树。

设x是T中的一个节点，T_x是T的以x为根的子树。

令 N_x 为 T_x 中叶子的数量

令 word(x) 为从根遍历 T 到节点 x 创建的单词

现在使用后缀树的定义我们得到：

单词的重复次数(x) = N_x 并且该单词的位置是每个叶子的标签

这个算法将是一个基本的树遍历，对于树中的每个节点计算 N_x，如果 N_x > 2 将其添加到您的结果中（如果您也想要位置，您可以添加每个叶子的标签）

伪代码 ：

输入 ：

我的序列

输出：

结果（重复次数和位置的单词列表）

算法 ：

T = suffixTree(mySequence)

对于 T 中的每个内部节点 X：

  T_X = subTree(T)
  N_X = Number of lead (T_X)
  if N_X >=2 :
  Result .add ( [word(X), N_X , list(label of leafs)] )

返回结果

例子 ：

让我们以维基百科中的后缀树为例：“BANANA”：

我们得到：

N_A = 3 so "A" repeats 3 times in position {1,3,5}
N_N=2  so "N" repeats 2 times  in position {2,4}
N_NA=2  so "NA" repeats 2 times in position {2,4}

我发现这篇论文似乎以与您相同的方式处理您的问题，所以是的，我认为您的方法是这样写：

使用后缀树拼写近似重复或常见的主题

提炼

我们在本文中提出了两种算法。第一个从字母表 Sigma 定义的序列中提取重复的基序。例如，Sigma可以等于{A，C，G，T}并且该序列代表DNA大分子的编码。搜索到的主题对应于同一字母表上的单词，这些单词在序列中出现最少 q 次，每次最多有 e 个不匹配（q 称为仲裁约束）。[...]

你可以下载看看，作者给出了你的算法的伪代码。

希望这可以帮助