Knuth-Morris-Pratt string search
Knuth-Morris-Pratt string search is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
< About Knuth-Morris-Pratt String Search Algorithm >
Emacs Lisp
<lang lisp> (defun kmp_compile_pattern (pattern)
"Compile pattern to DFA."
(defun create-2d-array (x y init) (let ((arr1 (make-vector x nil))) (dotimes (i x)
(aset arr1 i (make-vector y init)) )
arr1 ) ) (let* ((patLen (length pattern))
(R 256)
(restartPos 0)
(dfa (create-2d-array R patLen 0)))
(aset (aref dfa (elt pattern 0)) 0 1)
(let ((patPos 0)) (while (progn (setq patPos (1+ patPos)) (< patPos patLen))
(dotimes (c R) (aset (aref dfa c) patPos (aref (aref dfa c) restartPos)) )
(aset (aref dfa (elt pattern patPos)) patPos (1+ patPos)) (setq restartPos (aref (aref dfa (elt pattern patPos)) restartPos) ) )
) dfa ) )
(defun kmp_search (pattern text)
"Pattern search with KMP algorithm." (let ((dfa (kmp_compile_pattern pattern)))
(let ((textPos 0) (patPos 0) (N (length text)) (M (length pattern))) (while (and (< textPos N) (< patPos M))
(setq patPos (aref (aref dfa (elt text textPos)) patPos)) (setq textPos (1+ textPos)) )
(if (= patPos M) (- textPos M) N ) ) ) )
</lang>