Алгоритм Кнута — Морриса — Пратта

Function pos (t,p : String) : integer;
 var F : array[0..len] of integer;
     k,i : integer;
 {t - подстрока;p - соотвественно строка}
 {len - сумма длин строки и подстроки }
 begin
  F[1] := 0;
  k := 0;
  For i := 2 to length(T) do
   begin
    While (k > 0) and (T[k+1] <> T[i]) do
      k := F[k];
    if T[k+1] = T[i] Then
      Inc(k);              {функция Inc от числа сопоставима со строчкой число:=число+1}
    F[i] := k;
   end;
  k := 0;
  For i := 1 to length(P) do
   begin
    While (k > 0) and ( T[k+1] <> P[i]) do
      k := F[k];
    if T[k+1] = T[i] Then
      Inc(k);
    if k = length(T) Then
      Begin
       pos := i+length(t);
       {Здесь обрабатываются полученные данные после того как мы нашли подстроку,
        можно сделать результатом работы функции не только положение подстроки}

       Break
      End;
   end;
 end;
Алгоритм Кнута — Морриса — Пратта в Википедии

Отправить комментарий

Проверка
Антиспам проверка
Image CAPTCHA
...