4

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

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

如您所见，我只搜索连续的子字符串，这似乎是一个问题，因为所有压缩算法（至少我知道）都不关心连续性（LZ*），或者太简单而无法处理连续模式而不是单个数据项（RLE）。我认为使用后缀树由于同样的问题，

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

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

4

2 回答 2

3

后缀树相关算法在这里很有用。

一种在Dan Gusfield 的字符串、树和序列算法（第 9.6 章）中进行了描述。它使用分治法和后缀树的组合，时间复杂度为 O(N log N + Z)，其中 Z 是子串重复的次数。

同一本书描述了针对这个问题的更简单的 O(N 2 ) 算法，也使用了后缀树。

于 2012-11-28T11:30:21.873 回答
3

这是我用于类似问题的方法：

<?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) ...限制索引大小和字符串比较长度之类的东西来排除太“早”的过去事件

于 2012-11-28T11:44:27.230 回答