加入有重叠的列表

Question

我正在尝试创建一个函数来查找两个列表之间的重叠区域和 returns 将两个列表连接在一起的结果。重叠区域是第一个列表的最长后缀，它与第二个列表的前缀匹配，并且在结果序列中只出现一次。

> (list-overlap '(a a a t t t t) '(t t t t g g g g g))
(list 'a 'a 'a 't 't 't 't 'g 'g 'g 'g 'g)
> (list-overlap '(a a a) '(g g g))
(list 'a 'a 'a 'g 'g 'g)
> (list-overlap '(a t t a) '(t t a a))
(list 'a 't 't 'a 'a)

我创建了一个函数来检查完全重叠，但我不知道如何只搜索部分重叠然后完成问题。这是我的前缀部分：

(define (list-prefix? lst1 lst2)
  (or (null? lst1)
      (and (not (null? lst2))
           (equal? (first lst1 ) (first lst2))
           (list-prefix? (rest lst1 ) (rest lst2)))))

我原以为您会使用 (reverse ...) 并逐个检查每个元素，但是一旦我到达最后一个元素，我就无法删除其余元素，因为没有子字符串函数对于列表。

任何帮助都会很棒。在 ISL 中。

Answer 1

你的 list-prefix? 函数看起来是正确的，只是没有必要检查 (pair? lst2)：这排除了两个列表是同一个列表的可能性。你反而想要 (not (null? lst2)).

要确定重叠区域是什么，您只需遍历 lst1 并检查每个位置之后的列表是否是 lst2 的前缀，以及 return 第一个这样的子列表。

Answer 2

这是我的版本：

#lang htdp/isl
(define (list-prefix? lhs rhs)
  (or (empty? lhs)
      (and (not (empty? rhs))
           (eqv? (first lhs) (first rhs))
           (list-prefix? (rest lhs) (rest rhs)))))

(define (list-overlap lhs rhs)
  (if (list-prefix? lhs rhs)
      rhs
      (cons (first lhs) (list-overlap (rest lhs) rhs))))

请注意，如果 lhs 为空，则 list-prefix? returns 为真，因此这是一个充分的基本情况。

加入有重叠的列表

Join lists with overlap

scheme

racket