Информатика, программирование / Курсовая работа: Алгоритмы поиска подстроки в строке

Курсовая работа: Алгоритмы поиска подстроки в строке

Var n,i,j:Integer;

Begin

n:=Length(P);

Fl[1]:=0;

For i:=2 To n Do

Begin

j:=Fl[i-1];

While (j<>0) And (P[j]<>P[i-1]) Do j:= Fl[j];

Fl[i]:=j+1;

End;

End;

????????: ?????? ????? ?????? ????????? ???????, ???? ? ??? ???????????? ????????? ????? ??, ??-??????, ?????????? ???????-??????? ?????????? ????? m ???, ????????? ????? ???????? ?????????? k. ??? ??? ? ????? while ??? ??????????? (P[k]<k), ?? ?? ?????????? ?????? 0, ?? ??????????? ??? ????? ?? ????, ??? ??????????. ?????????? k ?????????? ?? 1 ?? ????? m ???. ??????, ?????????? k ???????? ????? ?? ????? 2m ???. ???????, ??? ????? ?????? ???? ????????? ???? O(m) [1, 2].
Листинг 3
? ?????? ?? ????????? ? ?????? ?????????, ??????? ????????? ? ?????? (??????? 4).
Листинг 4

Function KMPSearch(S,P:String):Integer;

{ Алгоpитм Кнута-Моpиса-Пpатта, устанавливающий }

{ вхождение непустой стpоки P в стpоку S }

Var Fl:TMas;

i,j,n,m:Integer;

Begin

n:=Length(S);

m:=Length(P);

PrefFunc(P,Fl);

j:=1;

For i:=1 To n Do

begin

While (j<>0) And (P[j]<>S[i]) do j:=Fl[j];

If j=m Then Break;

j:=j+1

end;

If (j=m) then Result:=i-j+1 Else Result:=0;

End;

К-во Просмотров: 489
Бесплатно скачать Курсовая работа: Алгоритмы поиска подстроки в строке