Алгоритм Кнута — Морриса — Пратта
Falk0ner, сб, 03/01/2009 - 19:48.
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;
Алгоритм Кнута — Морриса — Пратта в Википедии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;
Отправить комментарий