{
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