开发学院软件开发Delphi kmp模式匹配算法的pascal实现 阅读

kmp模式匹配算法的pascal实现

 2006-02-04 13:33:14 来源:WEB开发网   
核心提示:{ 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

Tags:kmp 模式 匹配

编辑录入:爽爽 [复制链接] [打 印]
[]
  • 好
  • 好的评价 如果觉得好,就请您
      0%(0)
  • 差
  • 差的评价 如果觉得差,就请您
      0%(0)
赞助商链接