Когда использовать алгоритмы Рабина-Карпа или КМП?

Я создал строку, используя следующий алфавит. {A,C,G,T}. И моя строка содержит более 10000 символов. Я ищу следующие шаблоны в нем.

• ATGGA
• TGGAC
• CCGT

Я попросил использовать алгоритм соответствия строк, который имеет время O(m+n).

m = pattern length
n = text length

Оба KMP and Rabin-Karp algorithms имеют это время работы. Каков наиболее подходящий алгоритм (между Rabin-Carp и KMP) в этой ситуации?

Ответы

Ответ 1

Если вы хотите найти несколько шаблонов в типовом виде, правильный выбор - использовать Aho-Corasick, который является некоторым обобщением KMP. Теперь в вашем случае вы ищете только 3 шаблона, поэтому может быть, что KMP не намного медленнее (не чаще трех раз), но это общий подход.

Rabin-Karp проще реализовать, если мы предположим, что столкновения никогда не произойдет, но если проблема, которую вы имеете, это типичный поиск строк в KMP, будет более стабильным независимо от того, какой у вас есть. Однако у Rabin-Karp есть много других приложений, где KMP не вариант.

Ответ 2

Если вам нужна наивысшая точность из-за соответствия небольшого набора (например, последовательности ДНК), вы захотите использовать алгоритм расстояния Хэмминга.

(Источник: https://arxiv.org/ftp/arxiv/papers/1401/1401.7416.pdf)