ruby - 在允许与 Ruby 不匹配的情况下查找子字符串

Question

我正在阅读有关在字符串中查找子字符串的后缀数组方法，请参阅 ( http://www.codeodor.com/index.cfm/2007/12/24/The-Suffix-Array/1845) 例如

sa = SuffixArray.new("abracadabra")
puts sa.find_substring("aca") 

其中 SuffixArray 是后缀数组的实现，find_substring 是一种用于搜索子字符串开始位置的方法。

我的问题是如何在允许子字符串中存在给定数量的不匹配的情况下实现此搜索？例如，

max_mismatches = 2
search_string ="abrazadabra"
substring ="aca"

sa = SuffixArray.new("search_string")
puts sa.find_substring("substring",max_mismatches)

其中不匹配可能被视为错误阈值。在这种情况下，它应该能够匹配“aza”并返回“aza”子字符串的起始位置。另请注意，“abr”有 2 个不匹配!所以应该先归还。理想情况下，该方法应返回所有可能出现的情况。

有什么想法吗？或其他解决此类问题的方法？ 谢谢

Answer 1

# checks whether two strings are similar,
# allowing given number of characters of difference
def similar? a, b, mismatches = 1
  a.chars.zip(b.chars).count{|ca, cb| ca != cb} <= mismatches
end

# in haystack, find similar strings to needle
def find_similar haystack, needle, mismatches = 1
  haystack.chars.each_cons(needle.length).map(&:join).select{|s|
    similar?(s, needle, mismatches)
  }
end

find_similar 'abracadabra', 'aca'
# => ["aca", "ada"] 
find_similar 'abracadabra', 'aca', 2
# => ["abr", "bra", "aca", "ada", "abr", "bra"] 

请随意更改 similar? 方法以匹配您对相似的定义。