搜索長連續的重複子串

我有一個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

搜索長連續的重複子串

回答

相關問題