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

Question

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

• ATGGA
• TGGAC
• CCGT

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

m = pattern length
n = text length

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

Answer 1

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

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