{
  Implementation of KMP Algorithm
}
PROGRAM Impl_KMP;

USES
    CRT;

CONST
     MAX_STRLEN = 255;

VAR
   next         : array [ 1 .. MAX_STRLEN ] of integer;
   str_s, str_t : string;
   int_i        : integer;

Procedure get_nexst( t : string );
Var
   j, k : integer;
Begin
     j := 1; k := 0;
     while j < Length(t) do
     begin
          if ( k = 0 ) or ( t[j] = t[k] ) then
          begin
               j := j + 1; k := k + 1;
               next[j] := k;
          end
          else k := next[k];
     end;
End;

Function index( s : string; t : string ) : integer;
Var
   i, j : integer;
Begin
     get_next(t);
     index := 0;
     i := 1; j := 1;
     while ( i <= Length(s) ) and ( j <= Length(t) ) do
     begin
          if ( j = 0 ) or ( s[i] = t[j] ) then
          begin
               i := i + 1; j := j + 1;
          end
          else j := next[j];
          if j > Length(t) then index := i - Length(t);
     end;
End;

BEGIN
     ClrScr;
     Write('s = ');
     Readln(str_s);
     Write('t = ');
     Readln(str_t);
     int_i := index( str_s, str_t );
     if int_i <> 0 then
     begin
          Writeln( 'Found ', str_t, ' in ', str_s, ' at ', int_i, '.' );
     end
     else
         Writeln( 'Cannot find ', str_t, ' in ', str_s, '.' );
END.

index函數用于模式匹配，t是模式串，s是原串。返回模式串的位置，找不到則返回0