Алгоритм поиска строк Кнута-Морриса-Пратта (или алгоритм KMP) ищет вхождения слова W в основной текстовой строке S, используя наблюдение, что когда происходит несоответствие, само слово содержит достаточную информацию, чтобы определить, где может начаться следующее совпадение, тем самым минуя повторную проверку ранее сопоставленных символов.
Основная идея алгоритма KMP заключается в использовании таблицы частичного соответствия, которая вычисляется из строки шаблона и предоставляет информацию о самом длинном правильном префиксе шаблона, который также является суффиксом каждого префикс шаблона.
Эта информация позволяет алгоритму пропускать части текста, которые не соответствуют шаблону, на основе того, что уже было сопоставлено. Таким образом, алгоритм KMP может избежать ненужных символьных сравнений сравнений и может работать намного быстрее, чем метод грубой силы.
Процесс:
I. Вычислите таблицу частичного совпадения для строки шаблона «ABABAC». Эта таблица сообщает нам, какая часть шаблона соответствует правильному суффиксу шаблона для каждого префикса шаблона.
Сгенерировать таблицу частичного соответствия
Таблица частичного совпадения вычисляется с использованием модифицированной версии префиксной функции из Z-алгоритма.
Таблица частичного соответствия (также называемая функцией отказа или функцией префикса) для строки шаблона обычно создается с использованием следующего алгоритма:
- Инициализируйте два указателя,
iиj, равными 0. - Создайте пустой список
tableтой же длины, что и шаблон:
pattern: A B A B C A B A A table: 0 0 0 0 0 0 0 0 0
3. Установите table[0] = 0, так как первый символ шаблона не имеет правильного префикса, который также является правильным суффиксом:
pattern: A B A B C A B A A
table: 0 0 0 0 0 0 0 0 0
^
4. Прокрутите оставшиеся символы шаблона.
(т. е. для i от 1 до len(pattern) - 1) [i = 1 ; j = 0]:
а. Если символ в позиции i равен символу в позиции j в шаблоне, установите table[i] = j + 1 и увеличьте как i, так и j.
pattern: A B A B C A B A A
table: 0 0 1 2 0 1 2 3 1
^ ^
б. Если символ в позиции i не равен символу в позиции j в шаблоне, установите table[i] на максимальное значение 0 и значение table[j-1], где j — предыдущее значение j.
я. Если j равно 0, установите table[i] = 0 и увеличьте i.
pattern: A B A B C A B A A
table: 0 0 1 2 0 1 2 3 1
^ ^
II. В противном случае установите для j значение table[j-1] и повторите шаг 4.
pattern: A B A B C A B A A
table: 0 0 1 2 0 1 2 3 1
^ ^
В результате table:
pattern: A B A B C A B A A table: 0 0 1 2 0 1 2 3 1
Эта таблица сообщает нам для каждой позиции в шаблоне, какова длина самого длинного правильного префикса шаблона, который также является правильным суффиксом подстроки, заканчивающейся в этой позиции. Например, table[3] = 2, потому что подстрока ABAB имеет два правильных префикса, которые также являются правильными суффиксами, а именно AB и B, и их длина равна двум.
Другой более простой пример:
II. Инициализируйте два индекса i и j равными 0, которые представляют текущие позиции в тексте и шаблоне соответственно.
III. Сравните символ в позиции i в тексте с соответствующим символом в позиции j в образце. Если они совпадают, увеличьте как i, так и j. Если они не совпадают, мы используем таблицу частичного совпадения, чтобы определить следующую позицию j.
IV. В нашем примере мы начинаем со сравнения первых символов текста и шаблона, которые оба имеют значение «A». Они совпадают, поэтому мы увеличиваем как i, так и j. Продолжаем таким образом, пока не дойдем до пятого символа шаблона, который имеет значение 'C'. На данный момент мы сопоставили префикс «ABABA» шаблона с подстрокой «ABABA» текста. Однако следующим символом шаблона является «C», который не соответствует соответствующему символу в тексте.
V. Используйте таблицу частичного совпадения, чтобы определить следующую позицию j. В частности, мы ищем значение таблицы частичного соответствия для предыдущего значения j (которое равно 3), чтобы определить следующее значение j. Это значение говорит нам, какая часть шаблона, который мы уже сопоставили, также соответствует текущему суффиксу шаблона. В этом случае значение таблицы частичного соответствия для j=3 равно 2, что означает, что префикс «ABA» шаблона соответствует суффиксу «BA» текущей подстроки «ABAB» текста. Поэтому устанавливаем j в 2 и продолжаем сравнивать символы.
VI. Повторяем шаги 3–4, пока не дойдем до конца текста или не найдем совпадение по шаблону. В этом случае следующим символом шаблона является «А», который соответствует соответствующему символу в тексте. Мы продолжаем сравнивать символы, пока не сопоставим весь шаблон в тексте, начиная с позиции 2.
В целом, алгоритм KMP способен эффективно искать шаблоны в тексте, используя информацию о шаблоне, чтобы избежать ненужных сравнений. Таблица частичного совпадения позволяет алгоритму пропускать части текста, которые не могут соответствовать шаблону, основываясь на том, что уже было сопоставлено.
Временная сложность алгоритма KMP составляет O(n + m), где n и m — длины текста и шаблона соответственно.
Это связано с тем, что алгоритм сравнивает каждый символ текста не более чем с одним символом шаблона и вычисляет таблицу частичного совпадения за время O(m). Это может быть намного быстрее, чем метод грубой силы, временная сложность которого в худшем случае составляет O(nm).
В целом, алгоритм KMP является мощным и эффективным алгоритмом сопоставления строк, который широко используется на практике.
Это хороший выбор для задач с большими строками текста и/или шаблона, а скорость является критическим фактором.
Код:
def partial_match_table(pattern):
"""
Constructs the partial match table for the KMP algorithm.
Args:
pattern (str): The pattern to construct the partial match table for.
Returns:
list[int]: The partial match table.
"""
table = [0] * len(pattern)
i, j = 1, 0
while i < len(pattern):
if pattern[i] == pattern[j]:
j += 1
table[i] = j
i += 1
elif j > 0:
j = table[j-1]
else:
i += 1
return table
def kmp_search(pattern: str, text: str) -> int:
# Step 1: Construct the partial match table
table = partial_match_table(pattern)
# Step 2: Perform the search
i, j = 0, 0
while i < len(text):
if pattern[j] == text[i]:
i += 1
j += 1
if j == len(pattern):
return i - j
elif j > 0:
j = table[j-1]
else:
i += 1
return -1
def check_kmp(pattern, text):
"""
Searches for the first occurrence of the pattern in the given text using the Knuth-Morris-Pratt algorithm and
prints out different statements based on the result of the search.
Args:
pattern (str): The pattern to search for.
text (str): The text to search in.
"""
result = kmp_search(pattern, text)
if result == -1:
print(f"The pattern '{pattern}' was not found in the text '{text}'.")
else:
print(f"The pattern '{pattern}' was found in the text '{text}' starting at index {result}.")
if __name__ == "__main__":
# Test 1)
pattern = "abc1abc12"
text1 = "alskfjaldsabc1abc1abc12k23adsfabcabc"
text2 = "alskfjaldsk23adsfabcabc"
check_kmp(pattern, text1)
check_kmp(pattern, text2)
# Test 2)
pattern = "ABABX"
text = "ABABZABABYABABX"
check_kmp(pattern, text)
# Test 3)
pattern = "AAAB"
text = "ABAAAAAB"
check_kmp(pattern, text)
# Test 4)
pattern = "abcdabcy"
text = "abcxabcdabxabcdabcdabcy"
check_kmp(pattern, text)
Альтернативная реализация:
Он следует тем же двум шагам, что и предыдущая реализация:
создание массива ошибок и поиск шаблона в тексте с использованием массива ошибок для эффективной обработки несоответствий.
Единственное отличие заключается в реализации функции get_failure_array, которая по-прежнему создает таблицу частичного соответствия, используя аналогичный алгоритм.
from __future__ import annotations
def kmp(pattern: str, text: str) -> bool:
"""
The Knuth-Morris-Pratt Algorithm for finding a pattern within a piece of text
with complexity O(n + m)
1) Preprocess pattern to identify any suffixes that are identical to prefixes
This tells us where to continue from if we get a mismatch between a character
in our pattern and the text.
2) Step through the text one character at a time and compare it to a character in
the pattern updating our location within the pattern if necessary
"""
# 1) Construct the failure array
failure = get_failure_array(pattern)
# 2) Step through text searching for pattern
i, j = 0, 0 # index into text, pattern
while i < len(text):
if pattern[j] == text[i]:
if j == (len(pattern) - 1):
return True
j += 1
# if this is a prefix in our pattern
# just go back far enough to continue
elif j > 0:
j = failure[j - 1]
continue
i += 1
return False
def get_failure_array(pattern: str) -> list[int]:
"""
Calculates the new index we should go to if we fail a comparison
:param pattern:
:return:
"""
failure = [0]
i = 0
j = 1
while j < len(pattern):
if pattern[i] == pattern[j]:
i += 1
elif i > 0:
i = failure[i - 1]
continue
j += 1
failure.append(i)
return failure
if __name__ == "__main__":
# Test 1)
pattern = "abc1abc12"
text1 = "alskfjaldsabc1abc1abc12k23adsfabcabc"
text2 = "alskfjaldsk23adsfabcabc"
assert kmp(pattern, text1) and not kmp(pattern, text2)
# Test 2)
pattern = "ABABX"
text = "ABABZABABYABABX"
assert kmp(pattern, text)
# Test 3)
pattern = "AAAB"
text = "ABAAAAAB"
assert kmp(pattern, text)
# Test 4)
pattern = "abcdabcy"
text = "abcxabcdabxabcdabcdabcy"
assert kmp(pattern, text)
# Test 5)
pattern = "aabaabaaa"
assert get_failure_array(pattern) == [0, 1, 0, 1, 2, 3, 4, 5, 2]
Визуализировано:
Спасибо за чтение и за вашу поддержку.
Кроме того, если вы хотите, чтобы я в следующий раз рассмотрел конкретную структуру данных/алгоритм, сообщите мне об этом в разделе комментариев.
