Algorithm: Simple Boyer/Moore


/* Computation of the last table */
FOR c := 'a' TO 'Z' DO
  last[c] := 0;
END
i := 1
WHILE i <= m DO
  last[pat[i]] = i
  i := i+1
END

/* Simple Boyer Moore */
i := 1
WHILE i <= n-m+1 DO
  j := m
  WHILE j >= 1 AND pat[j] = text[i+j-1] D
    j := j-1
  END
  IF j = 0 THEN RETURN TRUE
  i := i+MAX(1, j-last[text[i+j-1]])
END
RETURN FALSE

Time complexity: O ((n-m) · m)
Space complexity: O (1)
(The cardinality of the alphabeth is supposed to be constant)

Back to the Applet