Uh,
Last bmh-search had parens in wrong places.
Here is correct version.
(defun bmh-search (pattern text)
(declare (optimize (speed 3) (safety 0) (debug 0)
(compilation-speed 0) (space 0))
(type simple-base-string pattern text))
(check-type pattern simple-base-string)
(check-type text simple-base-string)
(let* ((n (length text))
(m (length pattern))
(skip (make-array char-code-limit
:element-type 'fixnum
:initial-element m)))
(declare (fixnum n m))
(when (= 0 m)
(return-from bmh-search 0))
(loop for k fixnum below m do
(setf (aref skip (char-code (aref pattern k))) (- m k 1)))
(loop for k fixnum = (1- m) then
(setf k (+ k (max 1 (aref skip (char-code (aref text k))))))
while (< k n)
do
(loop for j fixnum downfrom (1- m)
for i fixnum downfrom k
while (and (<= 0 j)
(char= (aref text i)
(aref pattern j)))
finally (if (= j -1)
(return-from bmh-search (1+ i)))))))
On Fri, 4 Oct 2002, Kimmo Takkunen wrote:
> (defun bmh-search (pattern text)
> (declare (optimize (speed 3) (safety 0) (debug 0)
> (compilation-speed 0) (space 0))
> (type simple-base-string pattern text))
> (check-type pattern simple-base-string)
> (check-type text simple-base-string)
> (let* ((n (length text))
> (m (length pattern))
> (skip (make-array char-code-limit
> :element-type 'fixnum
> :initial-element m)))
> (declare (fixnum n m))
> (when (= 0 m)
> (return-from bmh-search 0))
> (loop for k fixnum below m do
> (setf (aref skip (char-code (aref pattern k))) (- m k 1)))
> (loop for k fixnum = (1- m) then
> (setf k (+ k (max 1 (aref skip (char-code (aref text k))))))
> while (< k n)
> do
> (loop for j fixnum downfrom (1- m)
> for i fixnum downfrom k
> while (and (<= 0 j)
> (char= (aref text i))
> (aref pattern j))
> finally (if (= j -1)
> (return-from bmh-search (1+ i)))))))
Kimmo
--
((lambda (integer) ;; http://www.iki.fi/kt/
(coerce (loop for i upfrom 0 by 8 below (integer-length integer)
collect (code-char (ldb (byte 8 i) integer))) 'string))
100291759904362517251920937783274743691485481194069255743433035)
