Я создал строку, используя следующий алфавит.
{A,C,G,T}. И моя строка содержит более 10000 символов. Я ищу следующие шаблоны в нем.
Я попросил использовать алгоритм соответствия строк, который имеет время O(m+n).
m = pattern length
n = text length
Оба KMP and Rabin-Karp algorithms имеют это время работы. Каков наиболее подходящий алгоритм (между Rabin-Carp и KMP) в этой ситуации?
Если вы хотите найти несколько шаблонов в типовом виде, правильный выбор - использовать Aho-Corasick, который является некоторым обобщением KMP. Теперь в вашем случае вы ищете только 3 шаблона, поэтому может быть, что KMP не намного медленнее (не чаще трех раз), но это общий подход.
Rabin-Karp проще реализовать, если мы предположим, что столкновения никогда не произойдет, но если проблема, которую вы имеете, это типичный поиск строк в KMP, будет более стабильным независимо от того, какой у вас есть. Однако у Rabin-Karp есть много других приложений, где KMP не вариант.
Если вам нужна наивысшая точность из-за соответствия небольшого набора (например, последовательности ДНК), вы захотите использовать алгоритм расстояния Хэмминга.
(Источник: https://arxiv.org/ftp/arxiv/papers/1401/1401.7416.pdf)