Fandom

Delphi Programming

Knuth-Morris-Pratt algorithm

2,918pages on
this wiki
Add New Page
Talk1 Share

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.

Code Snippets
DatabasesFiles and I/OForms/WindowsGraphicsNetworkingMath and AlgorithmsMiscellaneousMultimediaSystemVCL

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.

Also on Fandom

Random Wiki