查找段落

中的所有重复模式我有一个问题，我必须找到句子中存在的所有重复模式。查找段落

例子：'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

回答

相关问题