输入:字符串S = AAGATATGATAGGAT.
输出:最大重复次数,如GATA(如位置3和8),GAT(如位置3,8和13)等等......
最大重复是子串t在S中发生k> 1次,并且如果t向左或向右延伸,则它将发生少于k次.
内部节点的叶子后代是后缀,每个后缀都有一个左侧字符.
如果所有叶子后代的左侧字符都不完全相同,则称为"左侧多样化"节点.
最大重复是左 - 多样的内部节点.
总体思路:
构建后缀树,然后在树上执行DFS(深度优先搜索)
对于每个叶子,用左侧字符标记它
对于每个内部节点:
如果至少有一个孩子标有*,则用*标记*
否则,如果其子标签不同,请标注*.
否则,所有孩子都有相同的标签,将其复制到当前节点
上述想法是否正确？伪代码怎么样？然后我可以尝试自己编写程序.