Шпоры по МПиПА / Строки / Алгоритм Кнута Морриса и Пратта / C / Описание / Алгоритм поиска Кнута Морриса Пратта

Алгоритм поиска Кнута, Морриса и Пратта.

Входные данные - строка, в которой ищется фрагмент, и искомая подстрока.

Выходные данные - позиция первого символа подстроки для ее первого вхождения в строке или -1 если подстрока в строке не найдена.

Внимание – отсчет позиции подстроки ведется с 0.

Код: KMP.cpp.

Исполняемый файл: KMP.exe.

Внимание – в связи с использованием в программе для ввода и вывода строк потоков ввода/вывода cin/cout входная строка не должна содержать пробелов, т.к. пробел рассматривается как символ конца ввода строки.

Примеры использования (распечатка листинга):

Knuth Morris Pratt Algoritm.

String: conglomerate

Substring: lom

Result: 4

Press any key to continue...

Knuth Morris Pratt Algoritm.

String: basketball

Substring: football

Result: -1

Press any key to continue...

Knuth Morris Pratt Algoritm.

String: hello_World,_hello

Substring: hello

Result: 0

Press any key to continue...