循环字符串问题

在scheme/planet上又看到了这道经典的面试题：写一个函数，判断字符串s1是否是s2循环移位得到的。

例如"WriteCode"就可以由"CodeWrite"循环移位得到。

一个trivial的实现如下。

有两个问题还没有想清楚：

1. 是否有更高效的算法？（可以用KMP找子串)

2. substring-at?和compare是尾递归吗？

#lang racket/base

; findout if pat is substring of str
(define (substring? pat str)
  (define pat-len (string-length pat))
  (define str-len (string-length str))
  (let substring-at? ((from 0))
    (if (> (+ pat-len from) str-len)
      #f
      (let compare ((index 0))
        (cond
          ((>= index pat-len) #t)
          ((char=? (string-ref pat index)
                   (string-ref str (+ from index)))
           (compare (+ index 1)))
          (else (substring-at? (+ from 1))))))))

; if s1 is a rotation of s2
; eg: ProgramRacket is a rotation of RacketProgram
(define (rotate-str? s1 s2)
  (and (= (string-length s1)
          (string-length s2))
       (substring? s1 (string-append s2 s2))))

; main starts here
(if (rotate-str?
      (vector-ref (current-command-line-arguments) 0)
      (vector-ref (current-command-line-arguments) 1))
  (printf "Yes\n")
  (printf "No\n"))