src/problems/kmp.lisp @ a95ed046cc2c

(defpackage :rosalind/kmp (:use :cl :rosalind :losh :iterate))
(in-package :rosalind/kmp)

(defparameter *input* ">Rosalind_87
CAGCATGGTATCACAGCAGAG")

(defparameter *output* "0 0 0 1 2 0 0 0 0 0 0 1 2 1 2 3 4 5 3 0 0")


(defun build-table (string)
  ;; https://www.inf.hs-flensburg.de/lang/algorithmen/pattern/kmpen.htm
  (iterate
    (with l = (length string))
    (with i = 0)
    (with j = -1)
    (with result = (make-array (1+ l) :initial-element -1))
    (while (< i l))
    (loop :while (and (>= j 0)
                      (not (char= (char string i)
                                  (char string j))))
          :do (setf j (aref result j)))
    (incf i)
    (incf j)
    (setf (aref result i) j)
    (returning (subseq result 1))))

(define-problem kmp (data stream) *input* *output*
  (multiple-value-bind (header sequence) (u:read-fasta data)
    (declare (ignore header))
    (string-join " " (build-table sequence))))