从字符串中查找子字符串
输入:字符串S= AAGATATGATAGGAT。
输出:最大重复，如GATA (在第3和第8位置)，GAT (在位置3，8和13)，等等。
- 最大重复是子字符串t在S中发生k>1次数，如果将t扩展到左或右，则出现的次数少于k次。
- 内部节点的叶后代是后缀，每个后缀都有一个左字符。
- 如果所有叶后代的左字符都不是完全相同的，则称为“左多样性”节点。
- 最大重复是左-多样的内部节点。
总体思路：
- 构建后缀树，然后在树上执行DFS (深度优先搜索)
- 对于每一片叶子，用它的左字符标记它。
- 对于每个内部节点：
- 如果至少有一个儿童被标记为*，那么将其标记为*。
- 否则，如果它的子标签是多样化的，用*标记。
- 否则，所有子节点都有相同的标签，将其复制到当前节点。
以上观点正确吗？伪码是怎么回事？然后我就可以自己写程序了。
回答 1
Stack Overflow用户
发布于 2011-10-14 11:40:01
你的想法是好的，但是有了后缀树，你可以做一些更容易的事情。
设T是序列的后缀树。 设x是T中的一个节点，T_x是根x的T的子树。 设N_x是T_x中的叶数 让word(x)是通过遍历T从根到节点x创建的单词。 现在，使用后缀树的定义，我们得到： 单词(X)= N_x的重复数和这个单词的位置是每个叶的标签
这个算法将是一个基本的树遍历，对于树中的每个节点计算N_x，如果N_x >2，将这个添加到结果中(如果您也想要这个位置，您可以添加每片叶子的标签)
伪码:
输入: mySequence 输出： 结果(与计数和位置重复的单词列表) 算法: T= suffixTree(mySequence) 对于T中的每个内部节点X： T_X = subTree(T) N_X =铅数(T_X)如果N_X >=2：.add ( word(X)，N_X，list(List of leafs) ) 返回结果
示例:
让我们以维基百科中后缀树的例子为例：“香蕉”：
我们得到：
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可以等于{A，C，G，T}，该序列表示DNA大分子的编码。搜索的主题对应于同一字母上的单词，该字母表在序列中出现最小次数q，每次最多出现e不匹配(q称为仲裁约束).
您可以下载并查看它，作者给出了您的算法的伪代码。
希望这能有所帮助
https://stackoverflow.com/questions/7763484
复制相似问题
腾讯云开发者
