В информатике алгоритм поиска строки Кнута-Морриса-Пратта (или алгоритм KMP ) ищет вхождения «слова» Wв основной «текстовой строке» S, используя наблюдение, что, когда происходит несоответствие, само слово содержит достаточную информацию. чтобы определить, где может начаться следующее совпадение, минуя, таким образом, повторную проверку ранее сопоставленных символов.
Алгоритм был придуман Джеймсом Х. Моррисом и независимо обнаружен Дональдом Кнутом «несколько недель спустя» из теории автоматов . [1] [2] Моррис и Воан Пратт опубликовали технический отчет в 1970 году. [3] Эти трое также совместно опубликовали алгоритм в 1977 году. [1] Независимо, в 1969 году, Матиясевич [4] [5] открыл аналогичный алгоритм, закодирован двумерной машиной Тьюринга при изучении проблемы распознавания сопоставления строк с образцом в двоичном алфавите. Это был первый линейный алгоритм сопоставления строк. [6]
Алгоритм сопоставления строк хочет найти начальный индекс mв строке S[], который соответствует искомому слову W[].
Самый простой алгоритм, известный как « грубая сила » или «наивный» алгоритм, заключается в поиске совпадения слов по каждому индексу m, т. е. позиции в искомой строке, которая соответствует символу S[m]. В каждой позиции mалгоритм сначала проверяет равенство первого символа искомого слова, S[m] =? W[0]т.е. Если совпадение найдено, алгоритм проверяет другие символы в искомом слове, проверяя последовательные значения индекса позиции слова, i. Алгоритм извлекает символ W[i]в искомом слове и проверяет равенство выражения S[m+i] =? W[i]. Если все последовательные символы совпадают в Wпозицииm, то в этой позиции в строке поиска будет найдено совпадение. Если индекс mдостигает конца строки, совпадения нет, и в этом случае говорят, что поиск «не пройден».
Обычно пробная проверка быстро отклоняет пробное совпадение. Если строки представляют собой равномерно распределенные случайные буквы, то вероятность совпадения символов составляет 1 из 26. В большинстве случаев пробная проверка отклоняет совпадение по начальной букве. Вероятность того, что первые две буквы совпадут, составляет 1 к 26 2 (1 к 676). Таким образом, если символы случайны, то ожидаемая сложность поиска строки S[]длины n составляет порядка n сравнений или O ( n ). Ожидаемая производительность очень хорошая. Если S[]1 миллион символов и W[]1000 символов, то поиск строки должен завершиться примерно после 1,04 миллиона сравнений символов.
Ожидаемая производительность не гарантируется. Если строки не случайны, то проверка пробы mможет потребовать много сравнений символов. В худшем случае две строки совпадают во всем, кроме последней буквы. Представьте, что строка S[]состоит из 1 миллиона символов, все из которых являются A , и что слово W[]состоит из 999 символов A , заканчивающихся последним символом B. Простой алгоритм сопоставления строк теперь проверяет 1000 символов в каждой пробной позиции, прежде чем отклонить совпадение и перейти к пробной позиции. Простой пример поиска строки теперь потребует около 1000 сравнений символов, умноженных на 1 миллион позиций, для сравнения 1 миллиарда символов. W[]Если длина k, то производительность в худшем случае равна O ( k ⋅ n ).