document.write('

由于题目要求最长重复子串，显然可以先求出所有的子串，然后通过比较各子串是否相等从而求出最长公共子串，具体的思路为：首先找出长度为n-1

的所有子串，判断是否有相等的子串，如果有相等的子串，那么就找到了最长的公共子串；否则找出长度为n-2的子串继续判断是否有相等的子串，依

次类推直到找到相同的子串或遍历到长度为1的子串为止。这种方法的思路比较简单，但是算法复杂度较高。下面介绍一种效率更高的算法：后缀数组

法。

后缀数组是一个字符串的所有后缀的排序数组。后缀是指从某个位置i开始到整个串末尾结束的一个子串。字符串r从第i个字符开始的后缀表示为

Suffix(i)，也就是Suffix(i)=r[i...len(r)]。例如：字符串“banana”的所有后缀如下：

所以“banana”的后缀数组为：[5,3,1,0,4,2]。由此可以把找字符串的重复子串的问题转换为从后缀排序数组中通过对比相邻的两个子串的公共串的

长度。在上例中3:ana与1:anana的最长公共子串为ana。这也就是这个字符串的最长公共子串。实现代码如下：

class CommonSubString:

#找出最长的公共子串的长度

def maxPrefix(self,s1,s2):

i=0

while i＜len(s1) and i＜len(s2):

if list(s1)[i]==list(s2)[i]:

i+=1

else:

break

i+=1

return i

#获取最长的公共子串

def getMaxCommonStr(self,txt):

n=len(txt)

#用来存储后缀数组

suffixes=[None]*n

longestSubStrLen=0

longestSubStr=None

#取到后缀数组

i=0

while i＜n:

suffixes[i]=txt[i:]

i+=1

#对后缀数组排序

suffixes.sort()

i=1

while i＜n:

tmp=self.maxPrefix(suffixes[i],suffixes[i-1])

if tmp＞longestSubStrLen:

longestSubStrLen=tmp

longestSubStr=suffixes[i][0:i+1]

i+=1

return longestSuloStr

if __name__=="__main__":

txt="banana"

c=CommonSubString()

print "最常的公共子串为: "+c.getMaxCommonStr(txt)

算法性能分析：

这种方法在生成后缀数组的复杂度为O(N)，排序的算法复杂度为O(NlogN*N)，最后比较相邻字符串的操作的时间复杂度为O(N)，所以算法的时间

复杂度为O(NlogN*N)。此外，由于申请了长度为N的额外的存储空间，因此空间复杂度为O(N)。

');