racket - How to compute the number of times pattern in one list appears in other list in Scheme

Question

I am stuck up in a Scheme program for about 5 hours. The program that I am working on should take two lists as input and then compute the number of times the pattern within the first list appears on the second list.

For example : > (patt '(b c) '(a b c d e b c)) ==> answer = 2

(patt '(a b c) '(a b c a b c d e a b c c c)) ==> answer = 3

(patt '((a b) c) '(a b (a b) c d e b c)) ==> answer = 1

Below is the code that I have till now.

(define (patt lis1 lis2)
  (cond
    ((null? lis1) 0)
    ((null? lis2) 0)
    [(and (> (length lis1) 1) (eq? (car lis1) (car lis2))) (patt (cdr lis1) (cdr lis2))]
    ((eq? (car lis1) (car lis2)) (+ 1 (patt lis1 (cdr lis2))))
    (else (patt lis1 (cdr lis2)))
    ))

Can someone please help me solve this. Thanks!

Answer 1

Consider the subproblem of testing if a list starts with another list.

Then do this for every suffix of the list. Sum up the count of matches.

If you want non overlapping occurrences, you can have the prefix match, return the suffix of the list so that you can skip over the matching part.

Also use equals? for structural equality, not eq? which is for identity.