A O(n) Solution to the Last Elisp Challenge

As I mentioned in the post, my An Elisp Challenge post was suggested by this Programming Praxis post. The next Programming Praxis post was a followup that discussed Booth’s Algorithm, which calculates how many left rotations a string must undergo to be lexicographically minimal. The thing about Booth’s algorithm is that it’s O(n) in the length, n, of the string. That gives us a way of making cyclep O(n) as well.

First, we need Booth’s algorithm. The following is pretty much a direct translation of the Python code in the Wikipedia article into Elisp

(defun booth (str)
  "Calculate the number of left rotations STR must undergo to be
lexicographically minimal."
  (let* ((str (concat str str))
         (n (length str))
         (fail (make-vector n -1))
         (k 0))
    (dolist (j (number-sequence 1 (1- n)) k)
      (let ((i (aref fail (- j k 1))))
        (while (and (/= i -1) (not (eq (aref str j) (aref str (+ i k 1)))))
          (when (< (aref str j) (aref str (+ i k 1)))
            (setq k (- j i 1)))
          (setq i (aref fail i)))
        (if (or (/= i -1) (eq (aref str j) (aref str (+ i k 1))))
            (aset fail (- j k) (1+ i))
          (when (< (aref str j) (aref str (+ i k 1)))
            (setq k j))
          (aset fail (- j k) -1))))))

Once we have Booth’s algorithm, the rest is easy:

(defun rotate-string (str n)
  "Rotate STR left N positions."
  (let ((k (mod n (length str))))
    (concat (substring str k) (substring str 0 k))))

(defun cyclep (s1 s2)
  "Check if S1 and S2 are cycles of each other."
  (string= (rotate-string s1 (booth s1)) (rotate-string s2 (booth s2))))

The rotate-string function does a left rotate of n positions on the string and the cyclep function ties everything together by rotating both strings into their lexicographically minimal forms and checking to see if they are equal.

All of this is sufficiently complicated that the previous O(n²) solution will probably be faster for reasonably sized strings. Still, it was fun to put this “faster” solution together even though I’m unlikely to need a cyclep of any speed.