permuted substrings


Write a function that accepts strings n and hs and returns -1 if there is no permutation of n appearing as a substring in hs or returns the index in hs of the left-most character of the left-most permutation of n.

 $ cat ps.rkt 
 #lang racket 
  
 (define (permutation-of:-in: needle hay-stack) ; smalltalk! 
  
   ; If some permutation of the string needle appears in the string 
   ; hay-stack, return the index of the permutation's left-most 
   ; character in hay-stack; otherwise return -1. 
  
   (define (canonical-string str) 
  
     ; Return the permutation of the given string in which the 
     ; characters are in ascending order. 
      
     (apply string (sort (string->list str) char>?))) 
  
   (let* 
     ((canonical-needle (canonical-string needle)) 
      (needle-size (string-length needle)) 
      (hay-stack-size (+ (- (string-length hay-stack) needle-size) 1))) 
  
     (let loop ((i 0)) 
       (cond 
         ((>= i hay-stack-size) 
            -1) 
         ((string=? 
            canonical-needle 
            (canonical-string (substring hay-stack i (+ i needle-size)))) 
            i) 
         (#t 
            (loop (+ i 1))))))) 
  
  
 (require rackunit) 
  
 (for-each 
   (lambda (t) (check-eq? (permutation-of:-in: (car t) (cadr t)) (caddr t))) 
   '(("xyz" "afdgzyxksldfm" 4) 
     ("wxyz" "asdfgzywpoiuy" -1) 
     ("wxyz" "" -1) 
     ("" "asdfgzywpoiuy" 0)  ; eh, questionable. 
     ("xyz" "asdfgzyxpoiuy" 5) 
     ("xyz" "xyza" 0) 
     ("xyz" "axyza" 1) 
     ("xyz" "axyz" 1))) 
      
 $ mzscheme ps.rkt 
  
 $