最长非重叠子环

Suffix array 是解决该问题的良好数据结构。

Programming Pearls 乔恩·本特利。

一个简单的算法是这样做的:

• 创建一个列表,列出字符串的每个片段,从[第一个字符,最后一个字符]开始,[第二个字符,第三个字符],直到[最后一个角色,最后一位字符]
• 这将所有具有共同前缀的字符串切片放在一起。然后,您可以迭代列表,比较每对字符,看看它们在开始时共享了多少个字符,如果它大于您的最大值,请记下来并将其设置为新的最大值

好吧,这里有一个疯狂的想法。

创建一个函数,确定O(n)中是否有长度为k的重复子字符串(其中n是文本的长度)。这可以通过使用滚动哈希来实现(参见维基百科 Rabin-Karp String Matching Algorithm )在线性时间内生成所有n个哈希值,并使用哈希表/BST(或映射、字典或您的语言所称的任何东西)存储相应的子字符串位置。在将当前哈希插入数据结构之前,我们检查是否以前见过它。如果以前见过,我们只需查找生成此哈希的索引,看看相应的子字符串是否是非重叠匹配。

现在我们可以在O(n)时间内找到一个k长的子字符串,我们只需运行二分查找即可找到最大的k,我们可以使用我们的函数找到一个不重叠的子字符串匹配。

Python中的代码如下

A=23
MOD=10007 # use a random value in the real world

def hsh(text):
    return sum([ord(c)*A**(len(text)-i-1) for i,c in enumerate(text)])%MOD

def k_substring(text, k):
    substrings={}
    cur=hsh(text[:k])
    pwr=(A**(k-1))%MOD
    substrings[cur]=[0]
    for i in xrange(k,len(text)):
        to_remove=(ord(text[i-k])*pwr)%MOD
        to_add=ord(text[i])
        cur-=to_remove
        if cur<0:
            cur+=MOD
        cur=(cur*A)%MOD
        cur=(cur+to_add)%MOD
        if cur in substrings:
            lst=substrings[cur]
            for index in lst:
                if index+k<=i-k+1 and text[index:index+k]==text[i-k+1:i+1]:
                    return index
            lst.append(i-k+1)
        else:
            substrings[cur]=[i-k+1]
    return -1

def longest_substring(text):
    hi,lo=len(text),0
    while hi>lo:
        mid=(hi+lo+1)>>1
        if k_substring(text,mid)==-1:
            hi=mid-1
        else:
            lo=mid
    index=k_substring(text,lo)
    return text[index:index+lo]

(如果不清楚,很抱歉。现在是早上6:30,我真的需要回去睡觉了:)