我在 Ruby 中找到了后缀数组的实现并对其进行了一些更改。这是我所拥有的:
class SuffixArray
def initialize(str)
@string = str
@suffix_array = []
(0...str.length).each do |i|
substring = @string[i...str.length]
@suffix_array << {:suffix=>substring, :index => i}
end
@sorted_suffix_array = @suffix_array.sort {|x,y| x[:suffix] <=> y[:suffix]}
end
def print_sorted
@sorted_suffix_array.each {|item| puts "#{item[:index]}=>#{item[:suffix]}"}
puts "total=>#{@sorted_suffix_array.size()}"
end
def print_unsorted
@suffix_array.each {|item| puts "#{item[:index]}=>#{item[:suffix]}"}
puts "total=>#{@suffix_array.size()}"
end
def find_substring(substring)
low = 0
high = @sorted_suffix_array.length
while(low <= high) do
mid = (low + high) / 2
comparison = @sorted_suffix_array[mid][:suffix]#[0..substring.length]
if comparison > substring
high = mid - 1
elsif comparison < substring
low = mid + 1
else
return @sorted_suffix_array[mid][:index]
end
end
end
end
它工作得很好,但它没有找到我想要的所有子字符串。例如
a = SuffixArray.new("there is a man who likes dogs")
puts a.find_substring("man") #won't be found
puts a.find_substring("who likes dogs") #will be found
puts a.find_substring("o likes dogs") #will be found
如何更改算法以使其找到我想要的所有子字符串?