An attempt to understand the KMP Failure Function.

kmp_failure_function.rb

class FailureFunction

    # build a table containing all of the maximum overlaps for a string
    def build_table(s)
        s_array = s.split(//)
        table = {} 
        for i in 0 .. s_array.size - 1
            word = s_array[0 .. i].join('')
            table[word] = max_overlap(word)
        end 

        table
    end

    protected

    # get the largest proper suffix possible that is also a prefix of s
    # this is the foundation of the KMP failure function table
    def max_overlap(s)
        s_array = s.split(//)

        prefixes = []
        suffixes = []

        for i in 0 .. s_array.size - 1
            prefixes << s_array[0 .. i].join('')
        end
            
        for i in 0 .. s_array.size - 1
            suffixes << s_array[s_array.size - 1 - i .. s_array.size - 1].join('')
        end

        prefixes.pop
        suffixes.pop

        biggest_at = -1
        for i in 0 .. prefixes.size - 1
            if prefixes[i] == suffixes[i]
                biggest_at = i
            end
        end

        if biggest_at > -1
            prefixes[biggest_at]
        else
            ""
        end
    end
end

require "test/unit"
class FailureFunctionTest < Test::Unit::TestCase
    def setup
        @failure_function = FailureFunction.new
    end

    def test_failure_function
        table = @failure_function.build_table("ABCDABD")
        assert_equal "",    table["A"]
        assert_equal "",    table["AB"]
        assert_equal "A",   table["ABCDA"]
        assert_equal "AB",  table["ABCDAB"]

        table = @failure_function.build_table("PARTICIPATE IN PARACHUTE")
        assert_equal "P",   table["PARTICIP"]
        assert_equal "PA",  table["PARTICIPA"]
        assert_equal "",    table["PARTICIPAT"]
        assert_equal "PAR", table["PARTICIPATE IN PAR"]
    end
end