Syntax10.Scn.FntSyntax10b.Scn.Fnt 8pdIStampElemsAlloc17 Mar 96 8FoldElemsNew 8  8K88 8 S8h888 h88 MODULE StringSearch; (* Christoph Steindl, CS, steindl@ssw.uni-linz.ac.at,  *) PROCEDURE BruteSearch* (VAR s: ARRAY OF CHAR; VAR pat: ARRAY OF CHAR): INTEGER; (** Returns the position of the first ocurrence of pat in s. Time: worst case: O(strlen(s) * strlen(pat)) average: O(strlen(s) + strlen(pat)) Comparisons: average: strlen(s) * strlen(pat) *) VAR i, j: INTEGER; ch: CHAR; BEGIN i := 0; ch := s[0]; WHILE ch # 0X DO IF ch = pat[0] THEN j := 1; WHILE (pat[j] # 0X) & (pat[j] = s[i + j]) DO INC(j) END ; IF pat[j] = 0X THEN RETURN i END END ; INC(i); ch := s[i] END ; RETURN -1 END BruteSearch;  PROCEDURE KMPSearch* (VAR s: ARRAY OF CHAR; VAR pat: ARRAY OF CHAR): INTEGER; (** Knuth-Morris-Pratt-Search Comparisons: worst case: strlen(s) * strlen(pat) *) VAR i, j, M, N: INTEGER; next: ARRAY 256 OF INTEGER; PROCEDURE InitNext; VAR i, j: INTEGER; BEGIN next[0] := -1; i := 0; j := -1; WHILE i < M DO WHILE (j >= 0) & (pat[i] # pat[j]) DO j := next[j] END ; INC(i); INC(j); IF pat[i] = pat[j] THEN next[i] := next[j] ELSE next[i] := j END END END InitNext; BEGIN j := 0; M := 0; WHILE pat[M] # 0X DO INC(M) END ; i := 0; N := 0; WHILE s[N] # 0X DO INC(N) END ; InitNext; WHILE (j < M) & (i < N) DO WHILE (j >= 0) & (s[i] # pat[j]) DO j := next[j] END ; INC(i); INC(j) END ; IF j = M THEN RETURN i - M ELSE RETURN i END END KMPSearch;  PROCEDURE BMSearch* (VAR s: ARRAY OF CHAR; VAR pat: ARRAY OF CHAR): INTEGER; (** Boyer-Moore-Search*) VAR i, j, k, patLen, sLen: INTEGER; skip: ARRAY 256 OF INTEGER; ch, patEnd: CHAR; PROCEDURE InitSkip; VAR i, j: INTEGER; BEGIN FOR i := 0 TO 255 DO skip[i] := patLen END ; FOR j := 0 TO patLen - 2 DO skip[ORD(pat[j])] := (patLen - 1) - j END END InitSkip; BEGIN patLen := 0; WHILE pat[patLen] # 0X DO INC(patLen) END ; sLen := 0; WHILE s[sLen] # 0X DO INC(sLen) END ; InitSkip; i := patLen - 1; patEnd := pat[i]; WHILE i < sLen DO ch := s[i]; IF ch = patEnd THEN j := i; k := patLen - 1; WHILE s[j] = pat[k] DO IF k = 0 THEN RETURN j END ; DEC(j); DEC(k) END END ; INC(i, skip[ORD(ch)]) END ; RETURN -1 END BMSearch;  PROCEDURE RKSearch* (VAR s: ARRAY OF CHAR; VAR pat: ARRAY OF CHAR): INTEGER; (** Robin-Karp-Search Time: average linear*) CONST q = 33554393; d = 32; VAR dM, h1, h2: LONGINT; i, M, N: INTEGER; BEGIN M := 0; WHILE pat[M] # 0X DO INC(M) END ; N := 0; WHILE s[N] # 0X DO INC(N) END ; dM := 1; h1 := 0; h2 := 0; FOR i := 1 TO M - 1 DO dM := (d * dM) MOD q END ; FOR i := 0 TO M - 1 DO h1 := (h1 * d + ORD(pat[i])) MOD q; h2 := (h2 * d + ORD(s[i])) MOD q END ; i := 0; WHILE h1 # h2 DO h2 := (h2 + d * q - ORD(s[i]) * dM) MOD q; h2 := (h2 * d + ORD(s[i + M])) MOD q; IF i > N - M THEN RETURN N END ; INC(i) END ; RETURN i END RKSearch;  END StringSearch.