- Алгоритм Кнута
-
Алгоритм Кнута — Морриса — Пратта (КМП-алгоритм) — алгоритм, осуществляющий поиск подстроки в строке.
Алгоритм был открыт Д. Кнутом и В. Праттом и, независимо от них, Д. Моррисом[1]. Результаты своей работы они опубликовали совместно в 1977 году[2].
Содержание
Постановка задачи
Даны образец и строка . Требуется определить индекс, начиная с которого строка содержится в строке . Если не содержится в — вернуть индекс, который не может быть интерпретирован как позиция в строке (например, отрицательное число). При необходимости отслеживать каждое вхождение образца в текст имеет смысл завести дополнительную функцию, вызываемую при каждом обнаружении образца.
Описание алгоритма и оценка времени работы
Рассмотрим сравнение строк на позиции , где образец сопоставляется с частью текста . Предположим, что первое несовпадение произошло между и , где . Тогда и .
При сдвиге вполне можно ожидать, что префикс (начальные символы) образца сойдется с каким-нибудь суффиксом (конечные символы) текста . Длина наиболее длинного префикса, являющегося одновременно суффиксом, есть префикс-функция от строки для индекса .
Это приводит нас к следующему алгоритму: пусть — префикс-функция от строки для индекса . Тогда после сдвига мы можем возобновить сравнения с места и без потери возможного местонахождения образца. Можно показать, что таблица может быть вычислена (амортизационно) за сравнений перед началом поиска. А поскольку строка будет пройдена ровно один раз, суммарное время работы алгоритма будет равно , где — длина текста .
См. также
Примечания
- ↑ Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4
- ↑ Donald Knuth; James H. Morris, Jr, Vaughan Pratt (1977). «Fast pattern matching in strings». SIAM Journal on Computing 6 (2): 323–350. DOI:10.1137/0206024.
Ссылки
Дональд Кнут Публикации Искусство программирования • «The Complexity of Songs» • Computers and Typesetting • Конкретная математика • Surreal Numbers • Things a Computer Scientist Rarely Talks About • Selected papers series Программное обеспечение ΤΕΧ • MIXAL (MIX • MMIX • GNU MDK) Шрифты AMS Euler • Computer Modern • METAFONT Грамотное программирование WEB • CWEB Алгоритмы Knuth's Algorithm X • Knuth–Bendix completion algorithm • Алгоритм Кнута — Морриса — Пратта • Knuth shuffle • Robinson–Schensted–Knuth correspondence • Trabb Pardo–Knuth algorithm Other Dancing Links • Knuth reward check • Премия Кнута • Man or boy test • Quater-imaginary base • -yllion • Potrzebie system of weights and measures Категории:- Поиск подстроки
- Дональд Кнут
Wikimedia Foundation. 2010.