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

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

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

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

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

Код: KMP.pas.

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

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

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...

Knuth Morris Pratt Algoritm.

String: hello World, hello

Substring:

Result: Wrong substring -1

Press any key to continue...