Изменения

[[Детерминированные_конечные_автоматы|Автомат ]] Кнута-Морриса-Пратта используется в алгоритмах , связанных с поиском образца в тексте, в том числе в реальном времени.

== Основные определения Суффикс-функция ==

|id = automatesuffix_func|definition = '''Конечным автоматом(finite-state machine)''' называется набор из пяти элементов:* Для строки <tex>p</tex> длиной <tex>Qm</tex> {{---}} множество состояний(конечное);* функция <tex>q_0 \in Qsigma_p \colon \Sigma^* \to \left\{1,2, \dots ,m\right\}</tex> {{называется '''суффикс---}} стартовое состояние;* функцией''', если она сопоставляет любой строке <tex>A \subset Qx</tex> {{---}} допускающие состояния;* , состоящей из символов алфавита <tex> \Sigma </tex> {{---}} алфавит;* , длину максимального суффикса <tex> \delta \colon Q \times \Sigma \to Qx</tex> {{---}} функция, определяющая правило перехода из одного состояния в другое по символу(''функция перехода'')являющегося префиксом <tex>p</tex>.

Пусть строка <tex>p</tex>="<tex>abaab</tex>". Вот несколько примеров значений суффикс---- ==== Пример конечного автомата ==== [[Файл:Fin_aut_exфункции для нее.png‎]]

Нулевое состояние обозначим стартовым, а допускающим будет только первое. Алфавит взят ;*<tex>\Sigma sigma_p("aba")=\left\{a,b\right\}3</tex> Такой автомат допускает все строки, в которых нечетное количество символов . :В данном случае вся строка является префиксом <tex>ap</tex>. ---- {{Определение|id ;*<tex>\sigma_p("bb")= suffix_func0</tex>. |definition = Для строки :В данном случае какой бы суффикс мы ни взяли, ни один из них не является префиксом <tex>sp</tex> длиной .;*<tex>m\sigma_p("aaab")=2</tex> функция . :В данном случае "<tex> \sigma \colon \Sigma^* \to \left\{1,2, \dots ,m\right\}ab</tex> называется '''суффикс-функцией''', если каждой строке сопоставляется длина ее максимального суффикса, являющегося " является префиксом <tex>sp</tex>., а все суффиксы длиннее {{---}}нет.

[[Детерминированные_конечные_автоматы|Автомат ]] строится на строке-образце <tex>sp</tex> длины <tex>m</tex>, которую в будущем мы будем искать в тексте.

Для [[Детерминированные_конечные_автоматы|автомата ]] Кнута-Морриса-Пратта:

* <tex> q_0 s = 0 </tex>* <tex> A T = \left\{m\right\} </tex>* <tex> \delta(q, a) = \sigma(sp[1 \dots q] + a) </tex>, где <tex>q</tex> {{---}} это состояние, <tex>a</tex> {{---}} символ, по которому осуществляется переход, a "<tex>+</tex>" {{---}} операция конкатенации (<tex>sp[1, 0] = \varepsilon </tex>).

Таким образом, если часть текста, в котором мы ищем образец, уже пропущена через [[Детерминированные_конечные_автоматы|автомат]], то текущее состояние отражает, сколько последних символов этой прочитанной части совпадает с началом нашего образца. Если мы пришли в допускающее состояние, значит последние <tex>m </tex> символов полностью совпадают с образцом и мы нашли включение.

*<center>''Символ <tex>a</tex> совпадает с <tex>q + 1</tex> символом строки <tex>sp</tex>. ''</center> * Это значит, что число последних символов текста, совпадающих с началом образца увеличилось на 1. Значит переход осуществляется в следующее состояние. В этом случае <tex>\delta(q, a) = q + 1</tex>.

*<center>''Символ <tex>a</tex> не совпадает с <tex>q + 1</tex> символом строки <tex>sp</tex>.Тогда заметим, что если к строке, являющейся максимальным [[Основные_определения,_связанные_со_строками#border|бордером]] предыдущего совпадения, добавить прочитанный символ, то как раз получится текущее окончание текста, совпадающее с началом образца. Таким образом, в этом случае <tex>\delta(q, a) = \delta(\pi_s(q), a)''</texcenter>.

* Тогда заметим, что если к строке, являющейся максимальным [[Основные_определения,_связанные_со_строками#border|бордером]] предыдущего совпадения, добавить прочитанный символ, то как раз получится текущее окончание текста, совпадающее с началом образца. Таким образом, в этом случае <tex>\delta(q, a) = \delta(\pi_p(q), a)</tex>, где <tex>\pi_spi_p(q)</tex> {{---}} [[Префикс-функция|префикс-функция, она возвращает длину максимального [[Основные_определения,_связанные_со_строками#border|бордера]] для префикса строки <tex>s</tex> длины <tex>qp</tex>). Исключением для этого случая является лишь нулевое состояние. Если считанный символ не совпадает с первым символом образца, то мы останемся в нулевом состоянии, так как по прежнему совпадением является пустая строка.

'''function''' make_kmp() '''for''' q = 0 '''to''' m '''for''' a <tex>\in \Sigma</tex> '''if''' q > 0 '''and''' a <tex>\ne</tex> sp[q + 1] <tex>\delta</tex>(q, a) = <tex>\delta</tex>(<tex>\pi</tex>(q), a) '''if''' c = sp[q + 1] <tex>\delta</tex>(q, a) = q + 1 '''else''' <tex>\delta</tex>(q, a) = q == Сравнение с другими алгоритмами поиска образца в тексте == При решении задачи поиска всех включений образца в текст также часто применяются алгоритмы Ахо-Корасик и Кнута-Морриса-Пратта. Алгоритм Ахо-Корасик использует автомат, построенный на основе приведенного здесь, и является расширением рассматриваемого алгоритма. Он применяется в несколько иных случаях {{---}} когда образцов для поиска несколько. И решает эту задачу быстрее, чем построение нескольких автоматов Кнута-Морриса-Пратта. Алгоритм Кнута-Морриса-Пратта решает ту же задачу, что и алгоритм с применением одноименного автомата. Однако он не может работать с текстом, вводимым в режиме реального времени, ему нужно заранее знать текст, в котором нужно искать образец. Также, если текст достаточно объемный, алгоритм Кнута-Морриса-Пратта будет использовать гораздо больше памяти, чем приведенный выше в данной статье. Однако, если текст небольшой и дан заранее, алгоритм Кнута-Морриса-Пратта будет работать быстрее.

*ISBN 978-5-8459-1794-2 '''Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн''' {{---}} Алгоритмы. Построение и анализ, стр.771{{---}}776. [[Категория: Алгоритмы и структуры данных]][[Категория: Поиск подстроки в строке]][[Категория: Автоматы и регулярные языки]]