Module: TraceVisualization::LongestCommonPrefix

Defined in:
lib/trace_visualization/longest_common_prefix.rb

Class Method Summary collapse

Class Method Details

.effective(a, pos, n) ⇒ Object

A linear-time algorithm to compute the longest common prefix information in suffix arrays from article: “Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Applications” Toru Kasai et al.

The method signature and variable names are stored under the specified work without changes.



10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
 
# File 'lib/trace_visualization/longest_common_prefix.rb', line 10

def self.effective(a, pos, n)
  rank = Array.new(n, 0)
  height = Array.new(n, 0)

  for i in 0 ... n
    rank[pos[i]] = i
  end

  h = 0
  for i in 0 ... n
    if (rank[i] > 0)
      j = pos[rank[i] - 1]
      while a[i + h] == a[j + h]
        h += 1
      end
      height[rank[i]] = h
      h -= 1 if h > 0
    end
  end

  height
end