Поиск подстроки в строке (алгоритм Кнута-Морриса-Пратта) - Free Pascal

Формулировка задачи:

Требуется написать программу которая ищет количество вхождений подстроки в строке, используя алгоритм кнута-морриса-пратта

Код к задаче: «Поиск подстроки в строке (алгоритм Кнута-Морриса-Пратта) - 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.

13   голосов, оценка 4.308 из 5


СОХРАНИТЬ ССЫЛКУ