查找所有重複的非重疊子串和循環

Question

我有一個複雜的字符串操作問題。 我有一個字符串，我將有循環，以及我需要識別和列出的循環。

'abcabcabcabcabcdkkabclilabcoabcdieabcdowabcdppabzabx' 

以下是可能的模式 - 不使用

ABC>

實際指標 - > 0,3,6,9,12,15,17，...... （對於重複串occurence指數）， 0,3,6,9（unique_occurence指數爲重複串，12，15，17 資格作爲有abc較長重複子串的一部分）

ABCD - > 12，15，17，12，15，17 （唯一occurence指數爲重複字符串）

BCDA（對於重複串occurence指數） - > 13，16，18 ..（次數指數爲重複串），（重複字符串的唯一出現索引），因爲它是 的重疊字符串abcd因此它不是必需的ab - > 0,3,6,9,12,15,17,25,27 .. （循環字符串的出現索引）， 25,27（循環字符串的唯一出現索引）。 .....

我想查找所有unique recurring occurences/recurrences，即循環字符串的所有唯一，非重疊值。正如剛纔提到的。和輸入字符串可能包含，

ALL環狀圖案（abcabcabcdefdefdeflkjlkjlkj =>abc，def，lkj是在週期復發，但bc，ab，bcab不期望，因爲它們是假陽性的結果） OR

單獨重複圖案（abcxabcdabcm =>abc是復發但不是循環的，即它們不adjecent） 或者

兩者的混合（abcabcabcabcabclkabcdokabcdhuabcd =>abc是一個循環的復發和abcd是一個非循環復發，我們需要找到兩個 - >僅abcd，abc是重複，不bc，ab，bcda等）

有人能提出一個解決方案ALGO這個問題聲明。我正在嘗試使用不會找到重疊結果的suffix_arrays。

Answer 1

構造一個散列，其中的鍵由給定字符串的所有唯一子字符串組成，該字符串在字符串中至少出現兩次（不重疊），對於每個鍵，該值都是字符串中所有偏移量的數組，密鑰（子字符串）的值開始。

代碼

def recurring_substrings(str) 
    arr = str.chars 
    (1..str.size/2).each_with_object({}) do |n,h| 
    arr.each_cons(n).map { |b| b.join }.uniq.each do |s| 
     str.scan(Regexp.new(s)) { (h[s] ||= []) << Regexp.last_match.begin(0) } 
    end 
    end.reject { |_,v| v.size == 1 } 
end 

實例

recurring_substrings 'abjkabrjkab' 
    #=> {"a"=>[0, 4, 9], "b"=>[1, 5, 10], "j"=>[2, 7], "k"=>[3, 8], "ab"=>[0, 4, 9], 
    # "jk"=>[2, 7], "ka"=>[3, 8], "jka"=>[2, 7], "kab"=>[3, 8], "jkab"=>[2, 7]} 

recurring_substrings "abcabcabcabcabcdkkabclilabcoabcdieabcdowabcdppabzabx" 
    #=> {"a"=>[0, 3, 6, 9, 12, 18, 24, 28, 34, 40, 46, 49], 
    # "b"=>[1, 4, 7, 10, 13, 19, 25, 29, 35, 41, 47, 50], 
    # "c"=>[2, 5, 8, 11, 14, 20, 26, 30, 36, 42], "d"=>[15, 31, 37, 43], 
    # "k"=>[16, 17], "l"=>[21, 23], "i"=>[22, 32], "o"=>[27, 38], "p"=>[44, 45], 
    # "ab"=>[0, 3, 6, 9, 12, 18, 24, 28, 34, 40, 46, 49], 
    # "bc"=>[1, 4, 7, 10, 13, 19, 25, 29, 35, 41], "ca"=>[2, 5, 8, 11], 
    # "cd"=>[14, 30, 36, 42], 
    # "abc"=>[0, 3, 6, 9, 12, 18, 24, 28, 34, 40], "bca"=>[1, 4, 7, 10], 
    # "cab"=>[2, 5, 8, 11], "bcd"=>[13, 29, 35, 41], 
    # "abca"=>[0, 6], "bcab"=>[1, 7], "cabc"=>[2, 8], "abcd"=>[12, 28, 34, 40], 
    # "abcab"=>[0, 6], "bcabc"=>[1, 7], "cabca"=>[2, 8], 
    # "abcabc"=>[0, 6], "bcabca"=>[1, 7], "cabcab"=>[2, 8]} 

說明

對於第一個例子上文中，步驟如下。

str = 'abjkabrjkab' 
arr = str.chars 
    #=> ["a", "b", "j", "k", "a", "b", "r", "j", "k", "a", "b"] 
q = str.size/2 # max size for string to repeat at least once 
    #=> 5 
b = (1..q).each_with_object({}) 
    #=> #<Enumerator: 1..5:each_with_object({})> 

我們可以看到該枚舉器將通過將其轉換爲數組來生成哪些元素。 （我會在下面再做幾次。）

b.to_a 
    #=> [[1, {}], [2, {}], [3, {}], [4, {}], [5, {}]] 

隨着計算的進行，將建立空的哈希值。

接着第一元件傳遞到塊並設置塊變量使用平行分配它（有時稱爲多個分配）。

n,h = b.next 
    #=> [1, {}] 
n #=> 1 
h #=> {} 

c = arr.each_cons(n) 
    #=> #<Enumerator: ["a", "b", "j", "k", "a", "b", "r", "j", "k", "a", "b"]:each_cons(1)> 

c是長度爲1的所有子串的陣列。在下一迭代中它將是長度爲2的所有子串等的陣列。見Emumerable#each_cons。

c.to_a # Let's see which elements will be generated. 
    #=> [["a"], ["b"], ["j"], ["k"], ["a"], ["b"], ["r"], ["j"], ["k"], ["a"], ["b"]] 
d = c.map { |b| b.join } 
    #=> ["a", "b", "j", "k", "a", "b", "r", "j", "k", "a", "b"] 
e = d.uniq 
    #=> ["a", "b", "j", "k", "r"] 

下一輪迭代，這將是

r = arr.each_cons(2) 
    #=> #<Enumerator: ["a", "b", "j", "k", "a", "b", "r", "j", "k", "a", "b"]: 
    # each_cons(2)> 
r.to_a 
    #=> [["a", "b"], ["b", "j"], ["j", "k"], ["k", "a"], ["a", "b"], 
    # ["b", "r"], ["r", "j"], ["j", "k"], ["k", "a"], ["a", "b"]] 
s = r.map { |b| b.join } 
    #=> ["ab", "bj", "jk", "ka", "ab", "br", "rj", "jk", "ka", "ab"] 
s.uniq 
    #=> ["ab", "bj", "jk", "ka", "br", "rj"] 

繼續，

f = e.each 
    #=> #<Enumerator: ["a", "b", "j", "k", "r"]:each> 
f.to_a # Let's see which elements will be generated. 
    #=> ["a", "b", "j", "k", "r"] 

s = f.next 
    #=> "a" 
r = (Regexp.new(s)) 
    #=> /a/ 
str.scan(r) { (h[s] ||= []) << Regexp.last_match.begin(0) } 

如果h還沒有一個關鍵s，h[s] #=> nil。 h[s] ||= []擴展爲h[s] = h[s] || []，在執行h[s] << Regexp.last_match.begin(0)之前將h[s]轉換爲空數組。那就是，h[s] = h[s] || [] #=> nil || [] #=> []。

在塊內MatchData對象用類方法Regexp::last_match檢索。 （或者，可以用全局變量$~代替Regexp.last_match，詳細信息請參閱Regexp上的「特殊全局變量」。）MatchData#begin返回當前匹配開始時的str的索引。

現在

h #=> {"a"=>[0, 4, 9]} 

其餘的計算是相似的，增加鍵 - 值對h直到已經在給定的例子已經構造。

Answer 2

作進一步處理@ CarySwoveland的出色答卷後：

def ignore_smaller_substrings(hash) 
    found_indices = [] 
    new_hash = {} 
    hash.sort_by{|s,_| [-s.size,s]}.each{|s,indices| 
    indices -= found_indices 
    found_indices |= indices 
    new_hash[s]=indices unless indices.empty? 
    } 
    new_hash 
end 

pp ignore_smaller_substrings(recurring_substrings('abcabcabcabcabcdkkabclilabcoabcdieabcdowabcdppabzabx')) 

哈希值是通過減少字符串長度（然後按字母順序）排序，指數只允許出現一次。

它輸出

{"abcabc"=>[0, 6], 
"bcabca"=>[1, 7], 
"cabcab"=>[2, 8], 
"abcd"=>[12, 28, 34, 40], 
"abc"=>[3, 9, 18, 24], 
"bca"=>[4, 10], 
"bcd"=>[13, 29, 35, 41], 
"cab"=>[5, 11], 
"ab"=>[46, 49], 
"bc"=>[19, 25], 
"cd"=>[14, 30, 36, 42], 
"b"=>[47, 50], 
"c"=>[20, 26], 
"d"=>[15, 31, 37, 43], 
"i"=>[22, 32], 
"k"=>[16, 17], 
"l"=>[21, 23], 
"o"=>[27, 38], 
"p"=>[44, 45]} 

這並不完全回答這個問題，但它來得有點接近。