# HG changeset patch
# User Steve Losh <steve@stevelosh.com>
# Date 1659664106 14400
# Node ID 0c68769a8788ec700d6acb00149b2c6e7437439a
# Parent  5616829c5d4ffeabd03fc1842bf07bc4a6c5ae70
KMP

diff -r 5616829c5d4f -r 0c68769a8788 src/problems/kmp.lisp
--- /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))))