这是一种明显具有二次时间复杂度的方法，但由于它不建立除长度为1的子字符串之外的任何子字符串对象，所以具有相对较低的常数因子。结果是一个2元组，
bestlen, list_of_results
其中bestlen是重复相邻块的最长子字符串长度，每个结果都是一个3元组，
start_index, width, numreps
这意味着被重复的子字符串是
the_string[start_index : start_index + width]
这些相邻元素中有numreps个。这总是如此。
bestlen == width * numreps
问题描述存在歧义。例如，考虑以下输出：
>>> crunch2("aaaaaabababa")
(6, [(0, 1, 6), (0, 2, 3), (5, 2, 3), (6, 2, 3), (0, 3, 2)])
因此，它找到了5种将“最长”的连续部分视为长度为6的方法：
- 将初始的“a”重复6次。
- 将初始的“aa”重复3次。
- 将最左边的“ab”重复3次。
- 将最左边的“ba”重复3次。
- 将初始的“aaa”重复2次。
它不返回介绍或结尾，因为这些可以从它返回的内容中轻易推断出来：
- 引言是
the_string[: start_index]。
- 结尾是
the_string[start_index + bestlen :]。
如果没有重复相邻块，则返回
(0, [])
其他例子（来自您的帖子）：
>>> crunch2("EEEFGAFFGAFFGAFCD")
(12, [(3, 4, 3)])
>>> crunch2("ACCCCCCCCCA")
(9, [(1, 1, 9), (1, 3, 3)])
>>> crunch2("ABCD")
(0, [])
如何实现的关键：假设您有相邻重复的块，每个块的宽度为
W。然后考虑当您将原始字符串与向左移动
W 的字符串进行比较时会发生什么：
... block1 block2 ... blockN-1 blockN ...
... block2 block3 ... blockN ... ...
如果你在同一位置获得了(N-1)*W个连续相等的字符，那么问题就解决了。但是这个方法也可以反过来使用：如果你向左移动W并找到(N-1)*W个连续相等的字符，那么你就可以得出结论：
block1 == block2
block2 == block3
...
blockN-1 == blockN
所以所有的 N 块必须是 block1 的重复。
因此，代码重复将原始字符串向左移动一个字符(的副本)，然后从左到右地遍历两个字符并标识相等字符的最长连续区间。这只需要每次比较一对字符。为了使“向左移”高效（常数时间），字符串的副本存储在 collections.deque 中。
注：在许多情况下，update() 执行了太多无用的工作，现已被替换。
def crunch2(s):
from collections import deque
def update(starti, zcount):
nonlocal bestlen
while zcount >= width:
numreps = 1 + zcount // width
count = width * numreps
if count >= bestlen:
if count > bestlen:
results.clear()
results.append((starti, width, numreps))
bestlen = count
else:
break
zcount -= 1
starti += 1
bestlen, results = 0, []
t = deque(s)
for width in range(1, len(s) // 2 + 1):
t.popleft()
zcount = 0
for i, (a, b) in enumerate(zip(s, t)):
if a == b:
if not zcount:
starti = i
zcount += 1
elif zcount:
update(starti, zcount)
zcount = 0
if zcount:
update(starti, zcount)
return bestlen, results
使用正则表达式
[由于大小限制已删除]
使用后缀数组
这是目前我找到的最快的方法，尽管仍然可能会导致二次时间复杂度。
请注意，找到重叠的字符串并不重要。如上面的crunch2()程序中解释的那样（在一些细节上解释），
- 给定字符串
s，其长度为n = len(s)。
- 给定整数
i和j，其中 0 <= i < j < n。
那么如果w = j-i，并且c是s[i:]和s[j:]之间共同前导字符的数量，则块s[i:j]（长度为w）从s[i]开始重复，共1 + c // w 次。
下面的程序直接遵循这个规则来查找所有重复相邻块，并记住总长度最大的那些块。返回与crunch2()相同的结果，但有时顺序不同。
后缀数组简化了搜索，但几乎没有消除它。后缀数组直接找到具有最大c的<i, j>, 但只限制搜索以最大化w * (1 + c // w)。最坏情况是形如letter * number的字符串，例如"a" * 10000。
我没有提供下面的sa模块的代码。它很啰嗦，任何后缀数组的实现都会计算相同的东西。suffix_array()的输出如下：
sa是后缀数组，是range(n)的唯一排列，使得对于所有i在range(1, n)中，s[sa[i-1]:] < s[sa[i]:]。
rank在这里没有使用。
对于range(1, n)中的i，lcp[i]给出从sa[i-1]和sa[i]开始的后缀之间的最长公共前缀的长度。
为什么Suffix Array胜出呢? 部分原因是它从不需要搜索以相同字母开头的后缀（通过构造，后缀数组使它们相邻），而检查重复块和是否为新的最佳值，无论块有多大或重复了多少次，都只需花费小的常数时间。如上所述，这只需在 C 和 w 上进行微不足道的算术计算即可。
免责声明: 对于我来说，后缀数组/树就像连续分数一样: 我能在必要时使用它们，并对结果感到惊奇，但它们让我头疼。敏感，敏感，敏感。
def crunch4(s):
from sa import suffix_array
sa, rank, lcp = suffix_array(s)
bestlen, results = 0, []
n = len(s)
for sai in range(n-1):
i = sa[sai]
c = n
for saj in range(sai + 1, n):
c = min(c, lcp[saj])
if not c:
break
j = sa[saj]
w = abs(i - j)
if c < w:
continue
numreps = 1 + c // w
assert numreps > 1
total = w * numreps
if total >= bestlen:
if total > bestlen:
results.clear()
bestlen = total
results.append((min(i, j), w, numreps))
return bestlen, results
一些时间记录
我将一个包含英语单词的小文件读入字符串 xs 中，每行一个单词:
>>> len(xs)
209755
>>> xs.count('\n')
25481
大约有25,000个单词，占用210,000个字节。这些算法的时间复杂度是二次方级别，所以我并不指望它运行得很快，但是经过数小时后，crunch2()仍在运行，而当我让它过夜时，它仍在运行。
这导致我意识到它的update()函数可能会做大量无用功，使得整个算法的时间复杂度变成立方级别。因此，我修复了这个问题。然后：
>>> crunch2(xs)
(44, [(63750, 22, 2)])
>>> xs[63750 : 63750+50]
'\nelectroencephalograph\nelectroencephalography\nelec'
这大约花费了38分钟，与我的预期相符。
正则表达式版本的crunch3()只需要不到十分之一秒的时间！
>>> crunch3(xs)
(8, [(19308, 4, 2), (47240, 4, 2)])
>>> xs[19308 : 19308+10]
'beriberi\nB'
>>> xs[47240 : 47240+10]
'couscous\nc'
如前所述，正则表达式版本可能无法找到最佳答案，但这里有另外一些因素: 默认情况下，“.”不匹配换行符，所以代码实际上进行了许多微小的搜索。文件中的每个约 25K 换行符都有效地结束了本地搜索范围。用re.DOTALL标志编译正则表达式代替（因此换行符不被特殊处理）：
>>> crunch3(xs) # with DOTALL
(44, [(63750, 22, 2)])
大约14分钟后。
最后，
>>> crunch4(xs)
(44, [(63750, 22, 2)])
在不到9分钟的时间内，构建后缀数组所需的时间非常微小（不到一秒钟）。这实际上相当令人印象深刻，因为即使是 brute force 正则表达式版本几乎完全“以 C 速度”运行，但速度仍比较慢。
但这是相对的。从绝对意义上讲，所有这些都还是非常慢的 :-(
注意：下一节中的版本将把时间缩短到不到5秒（！）。
巨大的加速
这个方法采用了完全不同的方法。 对于上面的大型字典示例，它可以在不到5秒的时间内得出正确答案。
我为此感到相当自豪;-) 这是出乎意料的，我还没有见过这种方法。 它不执行任何字符串搜索，只对索引集进行整数算术运算。
对于类似于
letter * largish_integer 的输入格式，它仍然非常缓慢。目前的做法是只要当前考虑长度的子串中至少存在两个（不一定是相邻的，甚至可能重叠的！）副本，就会增加 1。例如，在...中。
'x' * 1000000
它将尝试从1到999999的所有子字符串大小。
然而，似乎可以通过重复加倍当前大小（而不仅仅是添加1），保存每个步骤中的类别，并进行混合二分搜索来定位存在重复的最大子字符串大小，从而显著提高效率。
我会留下这个无疑枯燥无味的练习给读者完成。我的工作已经完成了;-)
def crunch5(text):
from collections import namedtuple, defaultdict
IxSet = namedtuple("IxSet", "s w")
bestlen, results = 0, []
def combine(xs, ys):
xw, yw = xs[0].w, ys[0].w
neww = xw + yw
result = []
for y in ys:
shifted = set(i - xw for i in y.s if i >= xw)
for x in xs:
ok = shifted & x.s
if len(ok) > 1:
result.append(IxSet(ok, neww))
return result
def check(s):
nonlocal bestlen
x, w = s.s.copy(), s.w
while x:
current = start = x.pop()
count = 1
while current + w in x:
count += 1
current += w
x.remove(current)
while start - w in x:
count += 1
start -= w
x.remove(start)
if count > 1:
total = count * w
if total >= bestlen:
if total > bestlen:
results.clear()
bestlen = total
results.append((start, w, count))
ch2ixs = defaultdict(set)
for i, ch in enumerate(text):
ch2ixs[ch].add(i)
size1 = [IxSet(s, 1)
for s in ch2ixs.values()
if len(s) > 1]
del ch2ixs
for x in size1:
check(x)
current_class = size1
while current_class:
current_class = combine(current_class, size1)
for x in current_class:
check(x)
return bestlen, results
更快的算法
crunch6() 程序在我的计算机上能够将一个大型字典实例处理到不到 2 秒。它结合了来自 crunch4() （后缀和 lcp 数组）和 crunch5()（在一组索引中查找给定步幅的所有算术级数）的思想。
与 crunch5() 相似，代码循环次数等于最长重复子串的长度加1（可以是重叠或者不重叠）。如果没有长度为n 的重复，则没有长度大于n 的重复。这样做会使寻找重复字符串更容易，因为这是一个可利用的限制条件。但是，当将“胜利”约束在相邻重复的情况下，这种方法就行不通了。例如，在“abcabc”中，没有长度为1的偶数相邻重复，但有一个长度为3的相邻重复。这样做貌似使得任何直接二分搜索都是徒劳无功的（相邻大小为n的重复的存在或不存在并不能说明是否存在其他大小的相邻重复）。
对于形如'x' * n 的输入，效果仍然不佳。其中包含了所有长度从1到n-1的重复字符串。
注意：我给出的所有程序都能够生成所有最大长度相邻块的分解方式。例如，在一个由9个“x”组成的字符串中，它表示它可以通过重复“x” 9 次或者重复“xxx” 3 次来得到。因此，令人惊奇的是，它们都可以用作分解算法;-)
def crunch6(text):
from sa import suffix_array
sa, rank, lcp = suffix_array(text)
bestlen, results = 0, []
n = len(text)
def genixs(minc, sa=sa, lcp=lcp, n=n):
i = 1
while i < n:
c = lcp[i]
if c < minc:
i += 1
continue
ixs = {sa[i-1], sa[i]}
i += 1
while i < n:
c = min(c, lcp[i])
if c < minc:
yield ixs
i += 1
break
else:
ixs.add(sa[i])
i += 1
else:
yield ixs
def check(s, w):
nonlocal bestlen
while s:
current = start = s.pop()
count = 1
while current + w in s:
count += 1
current += w
s.remove(current)
while start - w in s:
count += 1
start -= w
s.remove(start)
if count > 1:
total = count * w
if total >= bestlen:
if total > bestlen:
results.clear()
bestlen = total
results.append((start, w, count))
c = 0
found = True
while found:
c += 1
found = False
for s in genixs(c):
found = True
check(s, c)
return bestlen, results
总是快速且发布，但有时错误
在生物信息学中，这被研究为“串联重复”、“串联阵列”和“简单序列重复”（SSR）。您可以搜索这些术语以查找相当多的学术论文，其中一些声称具有最坏情况下的线性时间算法。
但是它们似乎分为两个阵营：
- 类似于上面的
crunch4()，但没有它的内部循环的那种线性时间算法实际上是错误的 :-(
- 算法过于复杂，即使尝试将它们转换为可运行代码都需要付出努力 :-(
在第一个阵营中，有几篇论文可以归结为crunch4a()，但是没有其内部循环。下面是一个例子：crunch4a()。这里有一个例子：
“SA-SSR：基于后缀数组的大型遗传序列中详尽且高效的SSR发现算法。”
Pickett等人
https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5013907/
crunch4a()总是快速的，但有时会出错。实际上，它为这里出现的每个示例找到了至少一个最大重复段，将较大的字典示例解决在几秒钟内，并且对于形式为'x' * 1000000的字符串没有问题。大部分时间都用于构建后缀和LCP数组。但是它可能失败：
>>> x = "bcdabcdbcd"
>>> crunch4(x)
(6, [(4, 3, 2)])
>>> crunch4a(x)
(0, [])
问题在于不能保证“相关”的后缀在后缀数组中是相邻的。以“b”开头的后缀排序如下：
bcd
bcdabcdbcd
bcdbcd
通过这种方法找到尾部重复块需要将第一个块与第三个块进行比较。这就是为什么
crunch4()有一个内部循环，尝试所有以相同字母开头的对。相关的对可以在后缀数组中的任意数量的其他后缀中分开。但这也使算法成为二次时间。
def crunch4a(s):
from sa import suffix_array
sa, rank, lcp = suffix_array(s)
bestlen, results = 0, []
n = len(s)
for sai in range(1, n):
i, j = sa[sai - 1], sa[sai]
c = lcp[sai]
w = abs(i - j)
if c >= w:
numreps = 1 + c // w
total = w * numreps
if total >= bestlen:
if total > bestlen:
results.clear()
bestlen = total
results.append((min(i, j), w, numreps))
return bestlen, results
O(n log n)
这篇论文看起来对我来说是正确的，尽管我没有编写它：
“Simple and Flexible Detection of Contiguous Repeats Using a Suffix Tree”
Jens Stoye, Dan Gusfield
https://csiflabs.cs.ucdavis.edu/~gusfield/tcs.pdf
要实现亚二次算法需要做出一些妥协。例如，"x" * n 具有形如 "x"*2、"x"*3 等的 n-1 个子字符串，因此仅这些字符串就有 O(n**2) 种。 因此，任何找到所有这些字符串的算法都必须至少是二次时间复杂度。
详细信息请参阅论文；-) 您要寻找的一个概念是“原语”：“S*n” 的重复只能表示为不能再用较短的字符串重复表达的S。例如，"x" * 10 是 primitive，但 "xx" * 5 不是。
通向 O(n log n) 的一步
crunch9() 是我在评论中提到的“暴力”算法的实现，来自于：
“The enhanced suffix array and its applications to genome analysis”
Ibrahim等人
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.93.2217&rep=rep1&type=pdf
那里的实现草图只能找出“分支串联”重复项，而我在这里添加了代码来推断任意数量的重复项，并包括非分支重复项。虽然它最坏情况下仍是 O(n**2)，但对于您在评论中提到的 seq 字符串来说，它比这里的其他任何程序都快得多。目前为止，它与大多数其他程序产生了（除了顺序外）相同的详尽报告。
论文继续努力将最坏情况削减为 O(n log n)，但这会使其变慢。因此，它更加努力地斗争。我承认我失去了兴趣；-)
def genlcpi(lcp):
lcp.append(0)
stack = [(0, 0)]
for i in range(1, len(lcp)):
c = lcp[i]
lb = i - 1
while c < stack[-1][0]:
i_c, lb = stack.pop()
interval = i_c, lb, i - 1
yield interval
if c > stack[-1][0]:
stack.append((c, lb))
lcp.pop()
def crunch9(text):
from sa import suffix_array
sa, rank, lcp = suffix_array(text)
bestlen, results = 0, []
n = len(text)
def gen_btr(text=text, n=n, sa=sa):
for c, lb, rb in genlcpi(lcp):
i = sa[lb]
basic = text[i : i + c]
rb += 1
hi = rb
while lb < hi:
mid = (lb + hi) // 2
i = sa[mid] + c
if text[i : i + c] < basic:
lb = mid + 1
else:
hi = mid
lo = lb
while lo < rb:
mid = (lo + rb) // 2
i = sa[mid] + c
if basic < text[i : i + c]:
rb = mid
else:
lo = mid + 1
lead = basic[0]
for sai in range(lb, rb):
i = sa[sai]
j = i + 2*c
assert j <= n
if j < n and text[j] == lead:
continue
yield (i, c, 2)
for start, c, _ in gen_btr():
numreps = 2
for i in range(start - c, -1, -c):
if all(text[i+k] == text[start+k] for k in range(c)):
start = i
numreps += 1
else:
break
totallen = c * numreps
if totallen < bestlen:
continue
if totallen > bestlen:
bestlen = totallen
results.clear()
results.append((start, c, numreps))
while start:
if text[start - 1] == text[start + c - 1]:
start -= 1
results.append((start, c, numreps))
else:
break
return bestlen, results
获得奖励积分 ;-)
对于一些技术含义而言，crunch11() 的最坏情况复杂度为 O(n log n)。除了后缀和最长公共前缀数组之外，还需要 rank 数组以及 sa 的逆序数组。
assert all(rank[sa[i]] == sa[rank[i]] == i for i in range(len(sa)))
正如代码注释所述，该程序还依赖于Python 3以提高速度（range()的行为）。这很浅显易懂，但要重写它将非常繁琐。
描述该程序的论文存在一些错误，因此如果该代码与您所阅读的内容不完全相符，请不要惊慌。相反，请按照他们所说的来实现，否则就会失败。
尽管如此，这段代码变得越来越复杂，我无法保证其中没有漏洞。但是，在我尝试过的所有情况下，它都能正常工作。
形如'x' * 1000000的输入仍然不够快，但显然不再是二次时间。例如，一个重复出现一百万次同一字母的字符串可以在接近30秒内完成。大多数其他程序则永远无法结束；-）
编辑：将genlcpi()更改为使用半开放式的Python范围；对crunch11()进行了大多数外观上的修改；增加了“提前退出”功能，可以节省最差情况（例如'x' * 1000000）下约三分之一的时间。
def genlcpi(lcp):
lcp.append(0)
stack = [(0, 0)]
for i in range(1, len(lcp)):
c = lcp[i]
lb = i - 1
while c < stack[-1][0]:
i_c, lb = stack.pop()
yield (i_c, lb, i)
if c > stack[-1][0]:
stack.append((c, lb))
lcp.pop()
def crunch11(text):
from sa import suffix_array
sa, rank, lcp = suffix_array(text)
bestlen, results = 0, []
n = len(text)
def gen_btr(text=text, n=n, sa=sa, rank=rank):
from itertools import chain
for c, lb, rb in genlcpi(lcp):
origlb, origrb = lb, rb
origrange = range(lb, rb)
i = sa[lb]
lead = text[i]
hi = rb
while lb < hi:
mid = (lb + hi) // 2
i = sa[mid] + c
if text[i : i+1] < lead:
lb = mid + 1
else:
hi = mid
lo = lb
while lo < rb:
mid = (lo + rb) // 2
i = sa[mid] + c
if lead < text[i : i+1]:
rb = mid
else:
lo = mid + 1
subrange = range(lb, rb)
if 2 * len(subrange) <= len(origrange):
for sai in subrange:
i = sa[sai]
ic = i + c
if ic < n:
r = rank[ic]
if r in origrange and r not in subrange:
yield (i, c, 2, subrange)
else:
for sai in chain(range(origlb, lb),
range(rb, origrb)):
ic = sa[sai] - c
if ic >= 0 and rank[ic] in subrange:
yield (ic, c, 2, subrange)
for start, c, numreps, irange in gen_btr():
crange = range(start - c, -1, -c)
if (numreps + len(crange)) * c < bestlen:
continue
for i in crange:
if rank[i] in irange:
start = i
numreps += 1
else:
break
totallen = c * numreps
if totallen < bestlen:
continue
if totallen > bestlen:
bestlen = totallen
results.clear()
results.append((start, c, numreps))
while start and text[start - 1] == text[start + c - 1]:
start -= 1
results.append((start, c, numreps))
return bestlen, results
aaaaaa，[ [] 6 a [] ]比[ [] 3 aa [] ]更好，因为在递归之后，您将得到[ [] 3 [ [] 2 a [] ] [] ]。 - Björn Lindqvistcrunch6所需的4秒时间。该要点中的字符串似乎触发了一些退化情况。 - Björn Lindqvistmax（lcp）+1）接近（或大于）len（text）/2的情况下都是如此 - 每个“crunch2”通道要简单得多比“crunch6”通道。 - Tim Peterscrunch9()编辑，它对于您的seq（以及我的字典示例）非常快。 - Tim Peters