python - 搜索长的连续重复子串

Question

我有一串 0 和 1。将“contiguous-double”定义为立即重复的子字符串。例如，字符串“011101010101110”可以分解为“011 1010 1010 1110”，可以压缩为“011(1010)1110”。

是否有一种好的算法可以在一个字符串中找到所有连续的 double ？我能想到的最好的是关于字符串长度的二次方:

def all_contiguous_doubles(s):
    for j in range(len(s)):
        for i in range(j):
            if s[i:j] == s[j:2*j - i]:
                print "%s(%s)%s" % (s[:i], s[i:j], s[2*j - i:])

Answer 1

在这里，我展示了我的动态规划解决方案，其时间复杂度为 O(n^2) 并且O(n^2) 的空间复杂度，其中 n 是原始字符串的长度。

下面我递归定义了函数dl(r,c)。如果您将 dl(r,c) 设为表格并按正确顺序填写，您将在 O(n^2) 内完成它。

定义:

char(i) = character at position i

substr(i) = substring starting from position i towards the end of original string.

dl(r,c) = length of common, non-overlapping prefix of substr(r) and substr(c).

dl(r,c) 的递归定义:

Since dl(r,c) is symmetric, we will only consider r <= c.

dl(r,c) = 0 when r == c. Because if the substring starts at the same point, it will always be overlapping.

dl(r,c) = 0 when char(r) != char(c). Because the prefix is not the same.

if char(r) == char(c),
    if dl(r+1,c+1) + 1 < c-r
        dl(r,c) = dl(r+1,c+1) + 1
    else
        dl(r,c) = dl(r+1,c+1)

dl(r,c) 中 dl(r,c) == c-r 的最大值就是你的答案。