从编程珍珠的15.2节
的C代码可以在这里查看： http://www.cs.bell-labs.com/cm/cs/pearls/longdup.c
当我使用后缀阵列实现它在Python：
example = open("iliad10.txt").read()
def comlen(p, q):
i = 0
for x in zip(p, q):
if x[0] == x[1]:
i += 1
else:
break
return i
suffix_list = []
example_len = len(example)
idx = list(range(example_len))
idx.sort(cmp = lambda a, b: cmp(example[a:], example[b:])) #VERY VERY SLOW
max_len = -1
for i in range(example_len - 1):
this_len = comlen(example[idx[i]:], example[idx[i+1]:])
print this_len
if this_len > max_len:
max_len = this_len
maxi = i
我发现了它非常缓慢idx.sort一步。 我认为这是缓慢的，因为Python中需要通过值而不是通过指针传递子（的C代码段）。
该测试的文件可以从以下地址下载这里
的C代码需要只有0.3秒完成。
time cat iliad10.txt |./longdup
On this the rest of the Achaeans with one voice were for
respecting the priest and taking the ransom that he offered; but
not so Agamemnon, who spoke fiercely to him and sent him roughly
away.
real 0m0.328s
user 0m0.291s
sys 0m0.006s
但为Python代码，它永远不会结束我的电脑（我等了10分钟，把它打死了）
任何人都不会有想法如何使代码效率？ （例如，小于10秒）
Answer 1:
我的解决方案是基于后缀阵列上。 它是由最长公共前缀的前缀加倍构成。 最坏情况下的复杂度是O（n（log n）的^ 2）。 任务“iliad.mb.txt”发生在我的笔记本电脑4秒。 该代码是很好的证明函数内部suffix_array和longest_common_substring 。 后一功能是短，并且可以被容易地修改为例如10个最长非重叠子串进行搜寻。 这Python代码比快原来的C代码（复制到这里）从问题，如果重复的字符串长度超过10000个字符。
from itertools import groupby
from operator import itemgetter
def longest_common_substring(text):
"""Get the longest common substrings and their positions.
>>> longest_common_substring('banana')
{'ana': [1, 3]}
>>> text = "not so Agamemnon, who spoke fiercely to "
>>> sorted(longest_common_substring(text).items())
[(' s', [3, 21]), ('no', [0, 13]), ('o ', [5, 20, 38])]
This function can be easy modified for any criteria, e.g. for searching ten
longest non overlapping repeated substrings.
"""
sa, rsa, lcp = suffix_array(text)
maxlen = max(lcp)
result = {}
for i in range(1, len(text)):
if lcp[i] == maxlen:
j1, j2, h = sa[i - 1], sa[i], lcp[i]
assert text[j1:j1 + h] == text[j2:j2 + h]
substring = text[j1:j1 + h]
if not substring in result:
result[substring] = [j1]
result[substring].append(j2)
return dict((k, sorted(v)) for k, v in result.items())
def suffix_array(text, _step=16):
"""Analyze all common strings in the text.
Short substrings of the length _step a are first pre-sorted. The are the
results repeatedly merged so that the garanteed number of compared
characters bytes is doubled in every iteration until all substrings are
sorted exactly.
Arguments:
text: The text to be analyzed.
_step: Is only for optimization and testing. It is the optimal length
of substrings used for initial pre-sorting. The bigger value is
faster if there is enough memory. Memory requirements are
approximately (estimate for 32 bit Python 3.3):
len(text) * (29 + (_size + 20 if _size > 2 else 0)) + 1MB
Return value: (tuple)
(sa, rsa, lcp)
sa: Suffix array for i in range(1, size):
assert text[sa[i-1]:] < text[sa[i]:]
rsa: Reverse suffix array for i in range(size):
assert rsa[sa[i]] == i
lcp: Longest common prefix for i in range(1, size):
assert text[sa[i-1]:sa[i-1]+lcp[i]] == text[sa[i]:sa[i]+lcp[i]]
if sa[i-1] + lcp[i] < len(text):
assert text[sa[i-1] + lcp[i]] < text[sa[i] + lcp[i]]
>>> suffix_array(text='banana')
([5, 3, 1, 0, 4, 2], [3, 2, 5, 1, 4, 0], [0, 1, 3, 0, 0, 2])
Explanation: 'a' < 'ana' < 'anana' < 'banana' < 'na' < 'nana'
The Longest Common String is 'ana': lcp[2] == 3 == len('ana')
It is between tx[sa[1]:] == 'ana' < 'anana' == tx[sa[2]:]
"""
tx = text
size = len(tx)
step = min(max(_step, 1), len(tx))
sa = list(range(len(tx)))
sa.sort(key=lambda i: tx[i:i + step])
grpstart = size * [False] + [True] # a boolean map for iteration speedup.
# It helps to skip yet resolved values. The last value True is a sentinel.
rsa = size * [None]
stgrp, igrp = '', 0
for i, pos in enumerate(sa):
st = tx[pos:pos + step]
if st != stgrp:
grpstart[igrp] = (igrp < i - 1)
stgrp = st
igrp = i
rsa[pos] = igrp
sa[i] = pos
grpstart[igrp] = (igrp < size - 1 or size == 0)
while grpstart.index(True) < size:
# assert step <= size
nextgr = grpstart.index(True)
while nextgr < size:
igrp = nextgr
nextgr = grpstart.index(True, igrp + 1)
glist = []
for ig in range(igrp, nextgr):
pos = sa[ig]
if rsa[pos] != igrp:
break
newgr = rsa[pos + step] if pos + step < size else -1
glist.append((newgr, pos))
glist.sort()
for ig, g in groupby(glist, key=itemgetter(0)):
g = [x[1] for x in g]
sa[igrp:igrp + len(g)] = g
grpstart[igrp] = (len(g) > 1)
for pos in g:
rsa[pos] = igrp
igrp += len(g)
step *= 2
del grpstart
# create LCP array
lcp = size * [None]
h = 0
for i in range(size):
if rsa[i] > 0:
j = sa[rsa[i] - 1]
while i != size - h and j != size - h and tx[i + h] == tx[j + h]:
h += 1
lcp[rsa[i]] = h
if h > 0:
h -= 1
if size > 0:
lcp[0] = 0
return sa, rsa, lcp
我喜欢这个解决方案在更复杂为O（n log n）的 ，因为Python有一个非常快的名单排序（list.sort），可能比需要的线性时间操作变得更快的方法从这篇文章中，这应该是O（n）的在非常随机串的特殊推定用小字母一起（典型为DNA分析GENOM）。 我在读2011高格说worsest情况为O（n log n）的我的算法，可以在实践中的速度比很多O（n）的算法，不能使用的CPU内存。
基于另一个答案的代码grow_chains比从问题最初的例子要慢19倍，如果文本包含重复的字符串8 KB长。 长时间反复文本是不典型的古典文学，但他们频繁例如，在“独立”学校家庭作业的集合。 程序不应该冻结就可以了。
我写了一个例子，测试使用相同的代码为Python 2.7，3.3 - 3.6。
Answer 2:
主要的问题似乎是，Python不通过复制切片： https://stackoverflow.com/a/5722068/538551
你必须使用一个memoryview ，而不是得到一个参考，而不是副本。 当我这样做，该程序后挂idx.sort功能（这是非常快的）。
我敢肯定，有一点点的工作，你可以得到其余的工作。
编辑：
上述变化将不会作为一个下拉更换工作，因为cmp不相同的方式工作的strcmp 。 例如，试试下面的C代码：
#include <stdio.h>
#include <string.h>
int main() {
char* test1 = "ovided by The Internet Classics Archive";
char* test2 = "rovided by The Internet Classics Archive.";
printf("%d\n", strcmp(test1, test2));
}
并比较结果这条巨蟒：
test1 = "ovided by The Internet Classics Archive";
test2 = "rovided by The Internet Classics Archive."
print(cmp(test1, test2))
C代码打印-3我的机器，而Python版本打印上-1 。 它看起来像示例C代码正在滥用的返回值strcmp （它是在使用qsort毕竟）。 我无法找到任何时文件strcmp将返回其他的东西比[-1, 0, 1]但添加printf到pstrcmp原代码表现出了很多那个范围的值（3，-31之外，5是第3个值）。
为了确保-3是不是有些错误代码，如果我们反向TEST1和TEST2，我们会得到3 。
编辑：
以上是有趣的琐事，但影响的代码，通过块方面实际上并不正确。 我意识到这一点，就像我关我的笔记本电脑，并留下了一个无线网络连接区......真的应该仔细检查一切我打之前Save 。
FWIW， cmp最肯定也适用于memoryview对象（打印-1如预期）：
print(cmp(memoryview(test1), memoryview(test2)))
我不知道为什么预期的代码不工作。 我的机器上打印出来的名单看起来并不如预期。 我会考虑这一点，并试图找到更好的解决办法，而不是在抓救命稻草。
Answer 3:
该算法引入Python的翻译：
from itertools import imap, izip, starmap, tee
from os.path import commonprefix
def pairwise(iterable): # itertools recipe
a, b = tee(iterable)
next(b, None)
return izip(a, b)
def longest_duplicate_small(data):
suffixes = sorted(data[i:] for i in xrange(len(data))) # O(n*n) in memory
return max(imap(commonprefix, pairwise(suffixes)), key=len)
buffer()可以得到一个子不复制：
def longest_duplicate_buffer(data):
n = len(data)
sa = sorted(xrange(n), key=lambda i: buffer(data, i)) # suffix array
def lcp_item(i, j): # find longest common prefix array item
start = i
while i < n and data[i] == data[i + j - start]:
i += 1
return i - start, start
size, start = max(starmap(lcp_item, pairwise(sa)), key=lambda x: x[0])
return data[start:start + size]
它需要5秒我的机器上的iliad.mb.txt 。
在原则上，可以找到使用在O（n）的时间和O（n）的存储器中的重复的后缀数组具有增强LCP阵列 。
注： *_memoryview()被弃用*_buffer()版本
更多的内存效率的版本（相对于longest_duplicate_small（））：
def cmp_memoryview(a, b):
for x, y in izip(a, b):
if x < y:
return -1
elif x > y:
return 1
return cmp(len(a), len(b))
def common_prefix_memoryview((a, b)):
for i, (x, y) in enumerate(izip(a, b)):
if x != y:
return a[:i]
return a if len(a) < len(b) else b
def longest_duplicate(data):
mv = memoryview(data)
suffixes = sorted((mv[i:] for i in xrange(len(mv))), cmp=cmp_memoryview)
result = max(imap(common_prefix_memoryview, pairwise(suffixes)), key=len)
return result.tobytes()
它需要17秒我的机器上的iliad.mb.txt 。 其结果是：
On this the rest of the Achaeans with one voice were for respecting
the priest and taking the ransom that he offered; but not so Agamemnon,
who spoke fiercely to him and sent him roughly away.
我不得不定义自定义函数比较memoryview对象，因为memoryview比较要么提高在Python 3的异常或在Python 2产生错误的结果：
>>> s = b"abc"
>>> memoryview(s[0:]) > memoryview(s[1:])
True
>>> memoryview(s[0:]) < memoryview(s[1:])
True
相关的问题：
查找最长的重复字符串，并将其给定的字符串中重复的次数
寻找长期重复子在一个巨大的字符串
Answer 4:
这个版本需要使用完全不同的算法，我大约-2007桌面上约17秒：
#!/usr/bin/env python
ex = open("iliad.mb.txt").read()
chains = dict()
# populate initial chains dictionary
for (a,b) in enumerate(zip(ex,ex[1:])) :
s = ''.join(b)
if s not in chains :
chains[s] = list()
chains[s].append(a)
def grow_chains(chains) :
new_chains = dict()
for (string,pos) in chains :
offset = len(string)
for p in pos :
if p + offset >= len(ex) : break
# add one more character
s = string + ex[p + offset]
if s not in new_chains :
new_chains[s] = list()
new_chains[s].append(p)
return new_chains
# grow and filter, grow and filter
while len(chains) > 1 :
print 'length of chains', len(chains)
# remove chains that appear only once
chains = [(i,chains[i]) for i in chains if len(chains[i]) > 1]
print 'non-unique chains', len(chains)
print [i[0] for i in chains[:3]]
chains = grow_chains(chains)
其基本思路是建立子和立场，他们occure的名单，因此无需一次又一次地比较相同的字符串。 结果列表的样子[('ind him, but', [466548, 739011]), (' bulwark bot', [428251, 428924]), (' his armour,', [121559, 124919, 193285, 393566, 413634, 718953, 760088])] 。 唯一的字符串被删除。 然后，每一个列表成员的增长由1个字符，并创建新的列表。 唯一的字符串将再次删除。 等等等等...
文章来源: Effcient way to find longest duplicate string for Python (From Programming Pearls)
