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(n2). 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(n2). 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.