require 'test/unit'

class TestKmp < Test::Unit::TestCase
  def kmp_search(string, substring)
    # Create a fail_table, which stands for if comparision fail at `pos` of substing,
    # where will be the beginning for the next round comparision.
    fail_table = [-1, 0]
    pos = 2
    cnd = 0
    while pos < substring.length
      if substring[pos - 1] == substring[cnd]
        fail_table[pos] = cnd + 1
        pos += 1
        cnd += 1
      else
        fail_table[pos] = 0
        pos += 1
        cnd = 0
      end
    end

    s = i = 0
    while s + i < string.length
      if string[s + i] == substring[i]
        i += 1
        return s if i == substring.length
      else
        s = s + i - fail_table[i]    # without fail_table, we will move `s` to right by 1 step
        i = fail_table[i] if i > 0   # without fail_table, we will compare substring from the beginning, aka, i = 0
      end
    end
  end

  def test_kmp_search
    assert_equal 15, kmp_search('ABC ABCDAB ABCDABCDABDE', 'ABCDABD')
    assert_equal nil, kmp_search('ABC ABCDAB ABCDABCDABDE', 'ABCDEF')
  end
end

[References]