SHARE
TWEET

Алгоритм КМП

EugenyB Feb 28th, 2013 120 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. Function Pos ( const Needle, HayStack : string ) : Integer;
  2. var
  3.   F: array of Integer;
  4.   k, i: integer;
  5. begin
  6.   SetLength(F, 1+Length(Needle)); // Строки индексируются с 1, динамические массивы - с 0.
  7.   F[1] := 0;
  8.   k := 0;
  9.   for i := 2 to Length(Needle) do
  10.   begin
  11.     while (k > 0) and (Needle[k+1] <> Needle[i]) do
  12.       k := F[k];
  13.     if Needle[k+1] = Needle[i] then
  14.       Inc(k);
  15.     F[i] := k;
  16.   end;
  17.   k := 0;
  18.   for i := 1 to Length(HayStack) do
  19.    begin
  20.     while (k > 0) and (Needle[k+1] <> HayStack[i]) do
  21.       k := F[k];
  22.     if Needle[k+1] = HayStack[i] Then
  23.       Inc(k);
  24.     if k = Length(Needle) Then
  25.     begin
  26.       Result := i-length(Needle)+1;
  27.       //Здесь обрабатываются полученные данные после того как мы нашли подстроку,
  28.       //можно сделать результатом работы функции не только положение подстроки хотя это и есть основная задача этой функции
  29.       Break;
  30.     end;
  31.   end;
  32. end;
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top