<p>(这个问题与音乐无关,但我以音乐为例
(一个用例。)</p>
<p>在音乐中,短语结构的一种常见方式是按音符序列
中间部分重复一次或多次。因此,这个短语
由引言、循环部分和输出部分组成。这里有一个
例如:</p>
<pre><code>[ E E E F G A F F G A F F G A F C D ]
</code></pre>
<p>我们可以“看到”介绍是[E],重复部分是[F G A]
F]输出为[cd]。因此,拆分列表的方法是</p>
<pre><code>[ [ E E E ] 3 [ F G A F ] [ C D ] ]
</code></pre>
<p>其中第一项是简介,第二项是
重复部分重复,第三部分输出</p>
<p>我需要一个算法来执行这样的拆分</p>
<p>但有一点需要注意,那就是可能有多种方法
拆分列表。例如,上述列表可分为:</p>
<pre><code>[ [ E E E F G A ] 2 [ F F G A ] [ F C D ] ]
</code></pre>
<p>但这是一个更糟糕的分裂,因为介绍和介绍更长。所以
该算法的标准是找到最大化
环件的长度,并使环件的组合长度最小
开场白和开场白。这意味着正确的分割</p>
<pre><code>[ A C C C C C C C C C A ]
</code></pre>
<p>是</p>
<pre><code>[ [ A ] 9 [ C ] [ A ] ]
</code></pre>
<p>因为导入和导出的组合长度是2,而
循环部分的长度为9</p>
<p>此外,虽然intro和outro可以是空的,但只有“true”重复是空的
允许。因此,不允许进行以下拆分:</p>
<pre><code>[ [ ] 1 [ E E E F G A F F G A F F G A F C D ] [ ] ]
</code></pre>
<p>可以将其视为为为数据找到最佳的“压缩”
序列请注意,在某些序列中可能没有任何重复:</p>
<pre><code>[ A B C D ]
</code></pre>
<p>对于这些退化情况,任何合理的结果都是允许的</p>
<p>以下是我对算法的实现:</p>
<pre><code>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]
</code></pre>
<p>我不确定它是否正确,但它通过了我做的简单测试
描述。问题是,这是一种缓慢的方式。我已经看过了
在后缀树上,但它们似乎不适合我的用例,因为
我要寻找的子字符串应该是不重叠和相邻的</p>