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

Объяснение кода листинга программы

  1. Алгоритм Кнута-Морриса-Пратта используется для поиска подстроки в строке.
  2. Функция PosCount принимает два аргумента: Needle (подстрока, которую нужно найти) и HayStack (строка, в которой нужно найти подстроку).
  3. Функция использует динамический массив F для хранения позиций, где встречается символ из подстроки.
  4. Переменная k используется для хранения позиции последнего найденного символа подстроки в строке HayStack.
  5. Переменная i используется для индекса символа подстроки, который сравнивается с символами строки HayStack.
  6. Функция инициализирует массив F и переменную k в начале работы.
  7. Цикл проходит по каждому симвопу подстроки Needle, начиная со второго символа.
  8. Внутри цикла используется вложенный цикл, который ищет позицию последнего символа подстроки в строке HayStack.
  9. Если символ подстроки найден в строке HayStack, то переменная k увеличивается на 1.
  10. Если символ подстроки не найден в строке HayStack, то переменная k уменьшается на 1, пока не будет найден символ подстроки или не будет достигнута позиция 0.
  11. После завершения вложенного цикла, функция увеличивает значение k на 1.
  12. Если переменная k равна длине подстроки, то функция увеличивает результат на 1.
  13. После завершения циклов, функция выводит результат на экран.
  14. В основной части программы, подстрока t и строка s считываются с помощью функции readln().
  15. Результат поиска подстроки выводится на экран с помощью функции writeln().

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

13   голосов , оценка 4.308 из 5
Похожие ответы