{ 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.