查找段落

中的所有重複模式我有一個問題，我必須找到句子中存在的所有重複模式。查找段落

例子：'camel horse game camel horse gym camel horse game' # This is the sanitized string as I will cleanup anything other than words before it.

['camel horse game', 0, 3, 6] # pattern and Index where it is repeated 
['camel horse', 0, 3, 6] # Another pattern, let it be a substring of the previous pattern

後綴樹是一種很好的解決方案，但我無法理解如何實現它的話，而不是字母/字符？

使用標準Duplicate Substringss solution將無法正常工作，因爲它會找到帶有一半/半字的模式。 - >'camel horse', 'amel hor' .... 'am h'這幾乎沒有任何用處。

在此先感謝。

來源

2016-10-23 Nishutosh Sharma

你可以爲任何你想要的字母表建立一個後綴樹。假設您創建了一個字母表，其中段落中的每個不同單詞都被視爲單個字母。然後，後綴樹會讓您在段落中找到重複的單詞序列，而不會將單詞分解爲單個字符。

來源

2016-10-23 19:06:50 templatetypedef

如果你可以用一些例子（任何語言）解釋它，或者通過支持答案可以拋出更多光的僞代碼，那將是非常好的。 –

我有疑問，如果我有超過26個不同的單詞，那麼我將不得不創建字母組合，那麼在這種情況下它將不會是可持續/可擴展的解決方案。 –

有許多算法（Farach的算法是第一個和更容易理解的算法之一），用於在字符串由整數值組成的情況下構建後綴樹。您可以爲每個單詞分配一個數字值，然後從這些數字中構建後綴樹。這是一個非常棘手的算法來編碼自己 - 就像任何用於構建後綴樹的算法一樣 - 但如果你想走這條路線，這可能是最優雅的方法。 – templatetypedef

我發現這個實施Ruby語言： - http://rubyquiz.com/quiz153.html

可以修改查找所有重複子。它有一個自定義的實現後綴樹。

來源

2016-10-26 09:42:36

你可以在答案中包含鏈接文章的相關部分嗎？一般來說，只有鏈接的答案是不鼓勵的，因爲它們往往會隨着時間的推移而變得陳舊。 – templatetypedef

def all_repeated_substrings 
    patterns = {} 
    size = $string.length 

    suffixes = Array.new(size) 
    size.times do |i| 
    suffixes[i] = $string.slice(i, size) 
    end 

    suffixes.sort! 

    recurrence = '' 
    at_least_size = 2 # the size to meet or exceed to be the new recurrence 
    distance = nil 
    neighbors_to_check = 1 

    (1...size).each do |i| 
    s1 = suffixes[i] 
    neighbors_to_check.downto(1) do |neighbor| 
     s2 = suffixes[i - neighbor] 
     s1_size = s1.size 
     s2_size = s2.size 
     distance = (s1_size - s2_size).abs 
     next if distance < at_least_size 
     recurrence = longest_common_prefix(s1, s2, distance) 
     if recurrence.size > 1 
     if patterns[:"#{recurrence}"] 
      patterns[:"#{recurrence}"] << (size - s2_size) 
     else 
      patterns[:"#{recurrence}"] = [(size - s2_size), (size - s1_size)] 
     end 
     end 
     at_least_size = recurrence.size + 1 
     if recurrence.size == distance 
     neighbors_to_check = [neighbors_to_check, neighbor + 1].max 
     else 
     neighbors_to_check = neighbor 
     end 
    end 
    end 
    return patterns 
end

改進後：http://rubyquiz.com/quiz153.html解決上述問題。我想，但有一個問題，它不適用於'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa'種循環模式。歡迎任何人改進上述代碼以實現循環模式。

來源

2016-10-26 09:45:51

回答

相關問題