Knuth-Morris-Pratt algorithm

Knuth-Morris-Pratt is an Algorithm for searching a text for a string. It's a very commonly used algorithm and is very fast. TODO: write about how it works.

a good explanation of how the KMP search algorithm works.

Here is a Delphi implementation of the kmp search algorithm.

function kmp_search_next( const W, S: string;
                          const T: array of Integer): Integer;
var
  m, i: Integer;
begin
  i := 1;
  m := 1;
  while ( ( ( m + i ) <= Length( S ) ) and ( i <= Length( W ) ) ) do begin
    if ( S[m + i] = W[i] ) then begin
      Inc( i );
    end
    else begin
      m := m + ( i - T[i] );
      if ( i > 1 ) then
        i := T[i];
    end;
  end;
  if m = Length( S ) then
    Result := 0
  else
    Result := m;
end;

function kmp_table( W: string ): array of Integer;
var
  i, j: Integer;
  T: array of Integer;
begin
  i := 3;
  j := 1;
  SetLength( T, Length( W ) + 1 );
  t[1] := 0;

  if ( Length( W ) > 1 ) then
    t[2] := 1;
  while ( i <= Length( W ) ) do begin
    if ( W[i - 1] = W[j] ) then begin
      T[i] := j + 1;
      Inc( j );
      Inc( i );
    end
    else if ( j > 1 ) then begin
      j := T[j];
    end
    else begin
      T[i] := 1;
      Inc( i );
      j := 1;
    end;
  end;
  Result := T;
end;

Use those two functions like this:

var
  str_to_search_for: string;
  str_to_search_in: string;
begin
  str_to_search_for := 'Word(s)';
  str_to_search_in  := 'String in which you will search for the word(s)';
  kmp_search_next( str_to_search_for, str_to_search_in, kmp_table( str_to_search_for ) );
end;

And the result of kmp_search_next will be the position of the word you searched for. If it isn't found it will return zero.