###

alias hbin me

A ruby implementation of the KMP algorithm

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
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]