algorithm - 发现字符串中的连续重复模式

Question

我正在尝试搜索字符串中子字符串重复的最大次数，这里有一些例子:

"AQMQMB" => QM (2x)
"AQMPQMB" => <nothing>
"AACABABCABCABCP" => A (2x), AB (2x), ABC (3x)

如您所见，我只搜索连续的子字符串，这似乎是个问题，因为所有压缩算法(至少我知道)都不关心连续性(LZ*)，或者太简单了处理连续模式而不是单个数据项 (RLE)。我想使用 suffix tree -相关算法也由于同样的问题而没有用。

我认为有一些生物信息学算法可以做到这一点，有人知道这样的算法吗？

编辑在第二个示例中，连续模式可能有多种可能性(感谢 Eugen Rieck 的通知，阅读下面的评论)，但在我的用例中，这些可能性中的任何一种实际上都是可以接受的。

Answer 1

这是我用来解决类似问题的方法:

<?php

$input="AACABABCABCABCP";

//Prepare index array (A..Z) - adapt to your character range
$idx=array();
for ($i="A"; strlen($i)==1; $i++) $idx[$i]=array();

//Prepare hits array
$hits=array();

//Loop
$len=strlen($input);
for ($i=0;$i<$len;$i++) {

    //Current character
    $current=$input[$i];

    //Cycle past occurrences of character
    foreach ($idx[$current] as $offset) {

        //Check if substring from past occurrence to now matches oncoming
        $matchlen=$i-$offset;
        $match=substr($input,$offset,$matchlen);
        if ($match==substr($input,$i,$matchlen)) {
            //match found - store it
            if (isset($hits[$match])) $hits[$match][]=$i;
            else $hits[$match]=array($offset,$i);
        }
    }

    //Store current character in index
    $idx[$current][]=$i;
}

print_r($hits);

?>

我怀疑它是 O(N*N/M) 时间，其中 N 是字符串长度，M 是字符范围的宽度。

它输出我认为是您示例的正确答案。

编辑:

此算法的优点是在运行时保持有效分数，因此它可用于流，只要您可以通过一些缓冲进行超前处理。它以高效的方式为此付出了代价。

编辑 2:

如果允许重复检测的最大长度，这将减少空间和时间的使用:通过诸如 if ($matchlen>MAX_MATCH_LEN) ...限制索引大小和字符串比较长度