查找最长的相邻重复不重叠子字符串

Question

（这个问题与音乐无关，但我以音乐为例用例。）

在音乐中，构造短语的一种常见方法是将音符序列中间部分重复一次或多次。因此，这句话由引言，循环部分和结尾组成。这是一个例如：

[ E E E F G A F F G A F F G A F C D ]

我们可以“看到”简介是[E E E]重复部分是[F G AF]，结尾是[C D]。因此，拆分列表的方法是

[ [ E E E ] 3 [ F G A F ] [ C D ] ]

其中第一项是简介，第二项是重复部分被重复，第三部分是结尾。

我需要一种算法来执行这种拆分。

但是有一个警告是，可能有多种方法可以拆分列表。例如，上面的列表可以分为：

[ [ E E E F G A ] 2 [ F F G A ] [ F C D ] ]

但是这是更糟糕的划分，因为前奏和尾奏的时间更长。所以该算法的标准是找到使环部分的长度，并最大程度地减少了简介和结尾。这表示[]的正确分割

[ A C C C C C C C C C A ]
是

[ [ A ] 9 [ C ] [ A ] ]
因为前奏和尾奏的总长度为2，而长度循环部分的值为9。

而且，虽然前奏和尾奏可以为空，但只有“ true”重复是允许的。因此，不允许进行以下拆分：

[ [ ] 1 [ E E E F G A F F G A F F G A F C D ] [ ] ]
将其视为找到最佳的“压缩”序列。请注意，在某些序列中可能没有任何重复：

[ A B C D ]
对于这些退化的情况，允许任何明智的结果。

这是我对算法的实现：

def find_longest_repeating_non_overlapping_subseq(seq):
    candidates = []
    for i in range(len(seq)):
        candidate_max = len(seq[i + 1:]) // 2
        for j in range(1, candidate_max + 1):
            candidate, remaining = seq[i:i + j], seq[i + j:]
            n_reps = 1
            len_candidate = len(candidate)
            while remaining[:len_candidate] == candidate:
                n_reps += 1
                remaining = remaining[len_candidate:]
            if n_reps > 1:
                candidates.append((seq[:i], n_reps,
                                   candidate, remaining))
    if not candidates:
        return (type(seq)(), 1, seq, type(seq)())

    def score_candidate(candidate):
        intro, reps, loop, outro = candidate
        return reps - len(intro) - len(outro)
    return sorted(candidates, key = score_candidate)[-1]
我不确定它是正确的，但是它通过了我已经进行的简单测试描述。它的问题在于它是减慢速度的方法。我看了后缀树，但它们似乎不适合我的用例，因为我需要的子字符串应该不重叠且相邻。

（（这个问题与音乐无关，但我将音乐用作一个使用案例的示例。）在音乐中，一种常见的构造短语的方法是将一系列中间部分重复一个或多个的音符序列。 。

Answer 1

[您似乎想做的几乎是LZ77压缩算法。您可以根据我链接到的Wikipedia文章中的参考实现检查代码。

Answer 2

这是我在执行的内容。它与您的非常相似，但是会跳过已检查为先前子字符串重复的子字符串。