Какова сложность наихудшего случая для KMP, когда цель состоит в том, чтобы найти все вхождения определенной строки?

Question

Я также хотел бы знать, какой алгоритм имеет сложность наихудшего случая для нахождения всех вхождений строки в другом.Похоже, алгоритм Бойера – Мура имеет линейную сложность по времени.

Answer 1

Алгоритм KMP имеет линейную сложность для поиска всех вхождений шаблона в строку, как алгоритм Бойера-Мураoo.Если вы попытаетесь найти шаблон типа «aaaaaa» в строке, такой как «aaaaaaaaa», как только у вас будет первое полное совпадение,

aaaaaaaaa
aaaaaa
 aaaaaa
      ^

таблица границ содержит информацию о том, что следующее максимально длинное совпадение (соответствующеедо самой широкой границы шаблона) префикса шаблона составляет всего один символ (полное совпадение эквивалентно несовпадению за концом шаблона в этом отношении).Таким образом, шаблон перемещается на одно место дальше, и поскольку из таблицы границ известно, что все символы шаблона, за исключением, возможно, последнего совпадения, следующее сравнение выполняется между последним символом шаблона и выровненным символом текста.В данном конкретном случае (найдите вхождения ^m в ⁿ ), что является наихудшим случаем для алгоритма простого сопоставления, алгоритм KMP сравнивает каждый текстовый символ ровно один раз.

На каждом шаге, по крайней мере, одна из

• позиция текстового символа сравнивается
• позиция первого символа шаблона по отношению к тексту

увеличивается, и никогда не уменьшается.Положение сравниваемого текстового символа может увеличиться не более чем в length(text)-1 раз, положение первого символа шаблона может увеличиться не более чем в length(text) - length(pattern) раз, поэтому алгоритм выполняет не более 2*length(text) - length(pattern) - 1 шагов.

.предварительная обработка (построение таблицы границ) занимает не более 2*length(pattern) шагов, таким образом, общая сложность составляет O (m + n), и больше не выполняется m + 2*n шагов, если m - длина шаблона и nдлина текста.

¹ Обратите внимание, что алгоритм Бойера-Мура, как обычно представлено, имеет сложность наихудшего случая O (m * n) для периодических шаблонов и текстов, таких как ^m и ⁿ , если требуются все совпадения, потому что после полного совпадения

aaaaaaaaa
aaaaaa
 aaaaaa
      ^
  <- <-
 ^

весь шаблон будет сравниваться повторно.Чтобы избежать этого, вам нужно помнить, как долго префикс шаблона все еще совпадает после сдвига после полного совпадения, и сравнивать только новые символы.

Answer 2

Существует длинная статья о KMP на http://en.wikipedia.org/wiki/Knuth-morris-pratt, которая заканчивается словами:

Поскольку две части алгоритма имеют, соответственно, сложности O (k) и O (n),сложность общего алгоритма составляет O (n + k).

Эти сложности одинаковы, независимо от того, сколько повторяющихся шаблонов в W или S. (конечная кавычка)

Так чтоОбщая стоимость поиска KMP является линейной по количеству символов строки и шаблона.Я думаю, что это справедливо, даже если вам нужно найти несколько вхождений шаблона в строке - и если нет, просто попробуйте поискать patternQ, где Q - символ, которого нет в тексте, и отметьте, где отображается состояние KMP.что все соответствует до Q.

Answer 3

Вы можете сосчитать функцию Пи для строки в O(length).KMP создает специальную строку длиной n+m+1 и рассчитывает на нее функцию Pi, поэтому в любом случае сложность будет O(n+m+1)=O(n+m)