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 ^{2})* 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.