返回计划中的子列表索引

Question

嗯，我是一个计划新手，我现在正在阅读SICP。我在网站上发现了一个问题。我花了2天的时间思考它，但仍然不知道可以请你们帮忙接着就，随即？

问题如下：

在计算机科学中一个常见的任务是找到一个模式的情况下，在一个数据集。在这个 问题中，您将编写一个过程（find-sublist空间子列表），该过程按顺序返回空间子列表的所有实例的开始索引列表 。注意，子列表的实例可以重叠，如在[]中给出的一个示例中那样。如果空间包含列表，则不需要在空间中的列表中找到 子列表，如下面的一个示例[ *]所示。您可能会认为 子列表不是空的。

Examples: 
(find-sublist '(7 1 2 3 4 1 2 1 2) '(1 2)) ; should return '(2 6 8) 
(find-sublist '(“a” “b” “c” “b” “d”) '(“d”)) ; should return '(5) 
(find-sublist '((1 2) (3 4) (5 . 6) 7 #f) '((3 4) (5 . 6))) ; should return '(2) 
(find-sublist '(1 1 1 2 1) '(1 1)) ; [*] should return '(1 2) 
(find-sublist '(9 1 2 3 (5 1 2 3) 1 2 3) '(1 2 3)) ; [**]should return '(2 6) 
(find-sublist '() '(#t #f #f)) ; should return '() 

Answer 1

我给你一些提示，找到你自己的答案，填补空白。第一步骤是一分为二的问题，首先谓词，告诉如果sublst是lst，从第一位置在lst开始：

(define (sublist? lst sublst) 
    (cond (<???> <???>) ; if sublst is empty return true 
     ((and <???> ; if lst is not empty and 
       <???>) ; the first element is equal in both lists 
     (sublist? <???> <???>)) ; advance recursion over both lists 
     (else <???>))) ; otherwise return false 

现在主要程序：在space每个位置这一个检查如果有一个子列表从那里开始（使用前面的过程）。如果是这样，建立一个列表作为当前索引的元素传递。请注意，我们需要跟踪当前指数的一个额外的参数：

(define (find-sublist space sublist) 
    (let loop ((space space)   ; initialize iteration variables 
      (idx 1)) 
    (cond (<???> <???>)    ; if space is empty return the empty list 
      ; if the list starting at current position is the sublist 
      ((sublist? space sublist) 
      (cons <???>    ; cons current index, advance recursion 
       (loop <???> <???>))) ; over the list and increment index 
      (else      ; otherwise just advance the recursion 
      (loop <???> <???>)))))  ; same as before 

Answer 2

你问自己一个问题：我的列表的第一个元素匹配的模式？如果是这样，请记录索引。如果你解决了这个问题，那么你将相同的逻辑应用到列表的其余部分。这是一个简单的解决方案。

(define (find-sublist list sub) 
    (define (sublist? list sub) 
    (or (null? sub) 
     (and (not (null? list)) 
      (equal? (car sub) (car list)) 
      (sublist? (cdr list) (cdr sub))))) 

    (let walking ((list list) (index 1) (indices '())) 
    (if (null? list) 
     (reverse indices) 
     (walking (cdr list) 
       (+ 1 index) 
       (if (sublist? list sub) 
        (cons index indices) 
        indices))))) 

这使用了一种称为'尾递归'的技术，它使计算等价于迭代。