Boyer-Moore string search: Difference between revisions
Content added Content deleted
m (→{{header|Emacs Lisp}}: minor cleanup) |
|||
| Line 16: | Line 16: | ||
;; Compile the pattern to a right most position map |
;; Compile the pattern to a right most position map |
||
(defun bm_compile_pattern (pattern) |
(defun bm_compile_pattern (pattern) |
||
(let |
(let ((patLen (length pattern)) |
||
( |
(rightMap (make-vector 256 -1)) |
||
(j -1)) |
|||
(while (> patLen (setq j (1+ j))) |
|||
| ⚫ | |||
rightMap |
rightMap |
||
) |
) |
||
| Line 28: | Line 29: | ||
"Boyer-Moore string search" |
"Boyer-Moore string search" |
||
(let ((startPos 0) |
(let ((startPos 0) |
||
(skip 0) |
|||
(result nil) |
|||
(rightMap (bm_compile_pattern pattern))) |
|||
(result nil)) |
|||
| ⚫ | |||
;; Continue this loop when no result and not exceed the text length |
;; Continue this loop when no result and not exceed the text length |
||
| Line 40: | Line 38: | ||
(let ((idx (length pattern)) (skip1 nil)) |
(let ((idx (length pattern)) (skip1 nil)) |
||
(while (and (not skip1) (>= (setq idx (1- idx)) 0)) |
|||
;; skip when the character at position idx is different |
|||
(when (/= (elt pattern idx) (elt text (+ startPos idx))) |
|||
;; looking up the right most position in pattern |
|||
(let ((right (aref rightMap (elt text (+ startPos idx))))) |
|||
(if (>= right 0) |
|||
(setq skip1 (max 1 (- idx right))) |
|||
(setq skip1 (1+ idx)) |
|||
) |
|||
(progn (setq skip1 (1+ idx))) |
|||
) |
|||
) |
|||
) |
|||
) |
|||
| ⚫ | |||
) |
|||
(setq result startPos) |
|||
| ⚫ | |||
(setq skip skip1) |
|||
) |
|||
) |
|||
) |
|||
) |
) |
||
result |
result |
||
) |
) |
||
) |
) |
||
(let ((pattern "alfalfa") |
(let ((pattern "alfalfa") |
||