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 $