1

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

是否有一个很好的算法来查找字符串中的所有连续双精度数？我能想到的最好的结果是关于字符串长度的二次方：

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:])
4

3 回答 3

1

在这里，我提出了我的动态编程解决方案，它的时间复杂度为O(n^2)，空间复杂度为 O(n^2)，其中 n 是原始字符串的长度。

下面我递归地定义函数 dl(r,c)。如果你把 dl(r,c) 做成一个表格并按照正确的顺序填写，你将在 O(n^2) 中完成它。

定义：

char(i) = 位置 i 处的字符

substr(i) = 从位置 i 开始到原始字符串末尾的子字符串。

dl(r,c) = substr(r) 和 substr(c) 的公共、非重叠前缀的长度。

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

由于 dl(r,c) 是对称的，我们只考虑 r <= c。

当 r == c 时，dl(r,c) = 0。因为如果子字符串从同一点开始，它将始终重叠。

当 char(r) != char(c) 时，dl(r,c) = 0。因为前缀不一样。

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是你的答案。

于 2012-11-20T02:20:48.187 回答
0

我会使用正则表达式 jan 提到/(.+)$1/

这是一个简单的算法，否则可能会起作用：

创建一个函数

get_largest(string, i, j)

它返回 i 和 j 之间的最大双精度。

我会使用 min(20, (ji)//2) 的 hash_size

现在说你的 hash_size 是 20，找到长度为 20 的最不常见的子串以及它出现的所有位置。（这可以通过哈希表快速完成）

现在假设它被发现的位置是 [10, 110, 320, 500, ..] 看看 string[10:110], string[110, 320], string[320, 500].. 等等。如果有的话这些子字符串出现多次，找到这些子字符串的所有位置，并使用上面的技术或修改版本检查是否有双精度。

如果您仍然没有找到包含长度为 20 的最不频繁子串的双精度数，我们现在可以递归地分治来搜索所有不包含最不频繁子串的最长子串。

希望在大多数情况下，这应该很快。

于 2012-11-20T01:12:42.777 回答
0

如果压缩确实是您的最终目标：

为什么不使用大小为 16 的查找表将字符串“0000”“0001”、“1010”等映射到它们各自的十六进制数“0-F”？

存储表示时：将二进制字符串转换为十六进制字符串序列？

您可能还想查找格雷码。其中在二进制序列中，前一个数字和当前数字恰好相差 1 位。

如果我们在表中有 0-F 的格雷码表示，则：

对于十六进制字符串中的字母：检查前一个或当前字母是否是“格雷码”顺序中的对应字母。如果是这样，您可以进一步压缩它。（不同的位也可以在中间 - 有些情况必须妥善处理'）

于 2012-11-20T06:39:32.453 回答