搜索长连续的重复子串

我有一个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:])

来源

2012-11-19 wye.bee

可以有二次方的许多双打。考虑字符串“111 ... 111” –

在任何类型的字符串搜索中避免二次行为的方法是跳过前缀。但是这对于只有两个字符值的字符串来说不太有用，所以它可能是一个不好的折衷。 – abarnert

预期字符串的字符范围是什么？ –

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

下面是一个简单的算法，可能会以其他方式工作：

创建函数

get_largest(string, i, j)

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

我会用最小的hash_size（20，（J-11）// 2）

现在说你的hash_size是20，发现长度为20的最罕见的子串并在其发生的所有位置。（这可以通过哈希表快速完成）

现在可以说它被发现的位置是[10,110,320,500，..] 看字符串[10：110]，字符串[110， 320]，字符串[320,500] ..等如果这些子字符串中的任何一个出现多次，请查找这些子字符串的所有位置，并使用上述技巧或修改后的版本检查double。

如果你还没有发现，含有长度为20的最罕见子了一倍，现在我们可以递归分而治之，以搜索所有不包含最罕见的子串最长子。

希望在大多数情况下，这应该是快速的。

来源

2012-11-20 01:12:42

在这里，我提出其具有时间的复杂性我的动态规划溶液为O（n^2）和为O（n^2）的空间复杂度，其中n是原始的字符串的长度。

下面我递归地定义函数dl（r，c）。如果您将dl（r，c）制成表格并按填写正确的顺序，您将在O（n^2）中完成它。

定义：

炭（ⅰ）=字符位置i

SUBSTR（ⅰ）=子从位置i开始向原始字符串的末尾。（r，c）= substr（r）和substr（c）的公共不重叠前缀的长度。 DL的

递归定义（R，C）：

由于DL（R，C）是对称的，我们将只考虑ř< = C。

当r == c时，dl（r，c）= 0。因为如果子字符串从相同的点开始，它将始终重叠。（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-20 02:20:48 Billiska

通过谨慎管理，空间复杂性可以降至“O（n）”。 – Billiska

如果压缩真的是你的最终目标：

为什么不能有大小16映射字符串“0000”“0001的查找表”，“1010”等，以各自的十六进制数“0-F” ？

当你存储的表示：将二进制字符串转换为一个十六进制字符串的序列？您可能也想查找Grey Code。在二进制序列中，以前的数字和电流恰好相差1位。

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

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

来源

2012-11-20 06:39:32 Arvind

搜索长连续的重复子串

回答

相关问题