Обнаружение последовательных повторяющихся паттернов в строке

Question

Я пытаюсь найти максимальное количество повторений подстроки внутри строки, вот несколько примеров:

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

Как вы можете видеть, я ищу только последовательные подстроки, и это кажется проблемой, потому что все алгоритмы сжатия (по крайней мере, я в курсе) не заботятся о последовательности ( LZ *) или слишком просты для обработки последовательных шаблонов. вместо отдельных элементов данных ( RLE). Я думаю, что использование алгоритмов дерева суффиксов также бесполезно из-за той же проблемы.

Я думаю, что есть некоторые алгоритмы биоинформатики, которые могут сделать это, кто-нибудь имеет представление о таком алгоритме?

Правка Во втором примере может быть несколько вариантов последовательных шаблонов (спасибо 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) ... ограничивает размер индекса и длину сравнения строк

Answer 2

Здесь полезны алгоритмы, связанные с суффиксным деревом.

Один из них описан в " Алгоритмах на строках, деревьях и последовательностях" Дэна Гасфилда (глава 9.6). Он использует комбинацию подхода "разделяй и властвуй" и деревьев суффиксов и имеет временную сложность O(N log N + Z), где Z - количество повторений подстроки.

В этой же книге описывается более простой алгоритм O (N²) для этой задачи, также с использованием суффиксных деревьев.