КМП-алгоритм
Материал из Википедии — свободной энциклопедии
![]() |
Эту статью следует викифицировать. Пожалуйста, оформите её согласно общим правилам и указаниям. |
КМП алгоритм назван по первым буквам фамилий создателей:Кнут,Моррис,Пратт.Этот алгоритм используется для поиска подстроки в строке(т.е.для для определения вхождения одной строки в другую). Поставим следующую задачу:имеется строка S и строка A и нужно определить индекс, начиная с которого строка A содержиться в строке S.Если A не содержиться в S - вернуть индекс равный -1.
Сложность алгоритма-О(n*log n).