Implementation of the algorithm described in the lecture: https://www.youtube.com/watch?v=NVJ_ELSbbew

z_algorithm.rb

module ZAlgorithm
  def z
    @z = Array.new(length, 0)
    @z[0] = length
    left = right = 0

    (1...length).each do |k|
      if k > right
        @z[k] = length_of_longest_prefix(k)
        unless @z[k].zero?
          left = k
          right = left + @z[k] - 1
        end
      else
        beta = right - k + 1
        z_prime = @z[k - left]

        case
        when z_prime < beta
          @z[k] = z_prime
          unless z_prime.zero?
            left = k
            right = k + @z[k] - 1
          end
        when z_prime > beta
          @z[k] = beta
          left = k
        when z_prime == beta
          @z[k] = length_of_longest_prefix(k, beta)
          left = k
          right = k + @z[k] - 1
        end
      end
    end

    @z
  end

  def length_of_longest_prefix(index, initial_value = 0)
    i = initial_value
    while self[index + i] == self[i]
      i += 1
    end
    i
  end
end

# Example usage:

string = "helloheyiamhello"
string.extend(ZAlgorithm)

string.z # => [16, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0]