KMP algorithm

kmp.rb

# frozen_string_literal: true

def kmp_table(pattern)
  i = 0
  j = 1
  table = [0]

  while j < pattern.size
    if pattern[i] == pattern[j]
      i += 1
    else
      i = table[i - 1] and next if i > 0
    end

    table[j] = i
    j += 1
  end

  return table
end

def kmp(string, pattern)
  i = 0
  j = 0
  table = kmp_table(pattern)
  results = []

  while true
    while i < string.size and j < pattern.size
      if string[i] == pattern[j]
        i += 1
        j += 1
      elsif j > 0
        j = table[j - 1]
      else
        i += 1
      end
    end

    break if j != pattern.size

    results << i - j
    j = table[j - 1]
  end

  return results
end

begin
  require 'bundler/inline'
rescue LoadError => e
  $stderr.puts 'Bundler version 1.10 or later is required. Please update your Bundler'
  raise e
end

require 'minitest/autorun'
require 'logger'

class KmpTest < Minitest::Test
  def test_multiple_match
    assert_equal [4, 14, 22, 37], kmp('cozacocacolacococacolacocacoladjejdeicocacola', 'cocacola')
  end

  def test_not_match
    assert_equal [], kmp('How do you do? Great thanks!', 'potato')
  end

  def test_overlapping_matches
    assert_equal [0, 8, 19], kmp('aaabbbbaaaabbbbaaaaaaabbbbaaaa', 'aaabbbbaaaa')
  end

  def test_small_repeative_pattern
    assert_equal [0, 2, 4, 8, 10, 12], kmp('abababaaabababaaab', 'aba')
    assert_equal [6, 14], kmp('abababaaabababaaaba', 'aaab')
  end
end