Поиск подстроки в строке (алгоритм Кнута-Морриса-Пратта) - Free Pascal
Формулировка задачи:
Требуется написать программу которая ищет количество вхождений подстроки в строке, используя алгоритм кнута-морриса-пратта
Решение задачи: «Поиск подстроки в строке (алгоритм Кнута-Морриса-Пратта)»
textual
Листинг программы
{$MODE OBJFPC} Function PosCount ( const Needle, HayStack : string ) : Integer; //с викиучебника {https://ru.wikibooks.org/wiki/Реализации_алгоритмов/Алгоритм_Кнута_—_Морриса_—_Пратта} var F: array of Integer; k, i: integer; begin Result:=0; SetLength(F, 1+Length(Needle)); // Строки индексируются с 1, динамические массивы - с 0. F[1] := 0; k := 0; for i := 2 to Length(Needle) do begin while (k > 0) and (Needle[k+1] <> Needle[i]) do k := F[k]; if Needle[k+1] = Needle[i] then Inc(k); F[i] := k; end; k := 0; for i := 1 to Length(HayStack) do begin while (k > 0) and (Needle[k+1] <> HayStack[i]) do k := F[k]; if Needle[k+1] = HayStack[i] Then Inc(k); if k = Length(Needle) Then begin Result := Result+1; //Здесь обрабатываются полученные данные после того как мы нашли подстроку, //можно сделать результатом работы функции не только положение подстроки хотя это и есть основная задача этой функции end; end; end; var s,t:string; begin write('String:');readln(s); write('Example:');readln(t); writeln('Result=',PosCount(t,s)); end.
Объяснение кода листинга программы
- Алгоритм Кнута-Морриса-Пратта используется для поиска подстроки в строке.
- Функция
PosCount
принимает два аргумента:Needle
(подстрока, которую нужно найти) иHayStack
(строка, в которой нужно найти подстроку). - Функция использует динамический массив
F
для хранения позиций, где встречается символ из подстроки. - Переменная
k
используется для хранения позиции последнего найденного символа подстроки в строкеHayStack
. - Переменная
i
используется для индекса символа подстроки, который сравнивается с символами строкиHayStack
. - Функция инициализирует массив
F
и переменнуюk
в начале работы. - Цикл проходит по каждому симвопу подстроки
Needle
, начиная со второго символа. - Внутри цикла используется вложенный цикл, который ищет позицию последнего символа подстроки в строке
HayStack
. - Если символ подстроки найден в строке
HayStack
, то переменнаяk
увеличивается на 1. - Если символ подстроки не найден в строке
HayStack
, то переменнаяk
уменьшается на 1, пока не будет найден символ подстроки или не будет достигнута позиция 0. - После завершения вложенного цикла, функция увеличивает значение
k
на 1. - Если переменная
k
равна длине подстроки, то функция увеличивает результат на 1. - После завершения циклов, функция выводит результат на экран.
- В основной части программы, подстрока
t
и строкаs
считываются с помощью функцииreadln()
. - Результат поиска подстроки выводится на экран с помощью функции
writeln()
.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д