python - 查找字符串中重叠和非重叠子字符串的数量

Question

PS:这不是 How to find the overlap between 2 sequences, and return it 的副本

[虽然我在上面的方法中询问解决方案是否可以应用于以下问题]

问:虽然我做对了，但它仍然不是一个可扩展的解决方案，而且绝对没有优化(得分低)。请阅读以下问题描述，并提供更好的解决方案。

问题:

为简单起见，我们要求前缀和后缀都为非空且短于整个字符串 S。字符串 S 的边界是任何既是前缀又是后缀的字符串。例如，"cut" 是字符串 "cutletcut" 的边框，字符串 "barbararhubarb" 有两个边框: “b” 和 “倒钩”。

class Solution { public int solution(String S); }

给定一个由 N 个字符组成的字符串 S，返回其最长边框的长度，该边框在给定字符串中至少有 3 个非重叠出现。如果 S 中没有这样的边界，函数应该返回 0。

例如，

• 如果 S = "barbararhubarb" 函数应该返回 1，如上所述；
• 如果 S = "ababab" 函数应该返回 2，作为 "ab" 和 "abab" 都是 S 的边界，但只有 "ab" 有 3 个不重叠的出现；
• 如果 S = "baaab" 函数应该返回 0，因为它唯一的边框 "b" 只出现了两次。

假设:

• N 是 [0..1,000,000] 范围内的整数；
• 字符串 S 仅包含小写字母 (a−z)。

复杂度:

• 预期的最坏情况时间复杂度是O(N)；
• 预期的最坏情况空间复杂度为 O(N)(不计算输入参数所需的存储空间)。

def solution(S):
    S = S.lower()
    presuf = []
    f = l = str()
    rank = []
    wordlen = len(S)
    for i, j in enumerate(S):
        y = -i-1
        f += S[i]
        l = S[y] + l
        if f==l and f != S:
            #print f,l
            new=S[i+1:-i-1]
            mindex = new.find(f)
            if mindex != -1:
                mid = f #new[mindex]
                #print mid
            else:
                mid = None
            presuf.append((f,mid,l,(i,y)))
    #print presuf
    for i,j,k,o in presuf:
        if o[0]<wordlen+o[-1]: #non overlapping
            if i==j:
                rank.append(len(i))
            else:
                rank.append(0)
    if len(rank)==0:
        return 0
    else:
        return max(rank)

我的解决方案时间复杂度是:O(N2) 或 O(N4)非常感谢帮助。

Answer 1

我的解决方案是结合 Rabin-Karp 和 Knuth–Morris–Pratt 算法。 http://codility.com/cert/view/certB6J4FV-W89WX4ZABTDRVAG6/details