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

[虽然如果可以应用于以下问题我请求上述方法的解决方案]

问：虽然我做对了,但它仍然不是一个可扩展的解决方案,绝对没有优化(分数低).阅读以下问题描述,并提供更好的解决方案.

题：

为简单起见,我们要求前缀和后缀非空并且比整个字符串S短.字符串S的边界是任何前缀和后缀的字符串.例如,“cut”是字符串“cutletcut”的边框,字符串“barbararhubarb”有两个边框：“b”和“barb”.

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

在给定由N个字符组成的字符串S的情况下,返回其最长边界的长度,该边界在给定字符串中至少有三次非重叠出现.如果S中没有这样的边界,则该函数应返回0.

例如,

>如果S =“barbararhubarb”,则函数应返回1,如上所述;
>如果S =“ababab”,则函数应返回2,因为“ab”和“abab”都是S的边界,但只有“ab”有三个非重叠的出现;
>如果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)
非常感谢.