kmp模式匹配算法的pascal实现

核心提示：{ 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

{
  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