--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/problems/kmp.lisp Thu Aug 04 21:48:26 2022 -0400
@@ -0,0 +1,30 @@
+(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))))