Irreal

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.

Here’s my solution to the recent Elisp challenge. It’s easy to be seduced by the notion of rotating one sequence to see if it’s equal to the other. That would work but the rotation is pretty expensive and the solution is O(n²). A simpler way is to concatenate one string with itself and then check if the other string is a substring. Here’s that solution in a nice, concise bit of Elisp:

(defun cyclep (s1 s2)
  (and (= (length s1) (length s2)) (search s1 (concat s2 s2))))

Note that the length check is necessary for more than just a speed optimization as it eliminates cases like “ab” “abc”.

The efficiency of the solution depends on how search works. If it is O(n) then so is cyclep. Sadly search uses a brute force method and is O(n²). On the other hand, I remember from long ago that the Microsoft C strstr function, which does essentially what search does, was actually faster than Boyer-Moore and other fancy O(n) implementations. That’s because it used a machine instruction to find the first character of the substring and then just did the expected byte-by-byte check after that. The Elisp search function uses a similar strategy but, of course, it doesn’t use the machine instruction to accelerate finding the beginning of candidate substrings.