A functional version of the KMP algorithm

For one of the projects I’m working on, I needed a compile-time version of the KMP algorithm in C++. I started by making the algorithm functional.


The Knuth-Morris-Pratt algorithm, useful for finding subsequences in a sequence, consists of two parts: one part looks at the subsequence to create a table of integers to see how much back-tracking is necessary if a match fails at a given point in the subsequence, and one part applies the matching and back-tracking to the sequence.

Following the mantra of “don’t delay until run-time what you can do at compile-time” I wanted to implement as much of the algorithm — namely the first part — at compile-time. As this means implementing it as a template meta-function, that also means implementing the algorithm in a functional dialect.

When I want to implement something that was originally written in something other than a functional dialect as functional code, Haskell is usually my language of choice, so I implemented the algorithm as an explicit recursion (which is easier to translate to a meta-function than a fold).

Here’s the code:

-- KMP algorithm
kmp_table w =
    build w initial_t initial_pos initial_cnd
    where
        initial_t = [-1, 0]
        initial_pos = 2
        initial_cnd = 0
        build w t pos cnd = 
            if pos >= length w
            then t
            else
                if (w!!(pos - 1)) == (w!!cnd)
                then build w (t ++ [cnd + 1]) (pos + 1) (cnd + 1)
                else if cnd > 0
                     then build w t pos (t!!cnd)
                     else build w (t ++ [0]) (pos + 1) cnd

Translating this to a C++ template is a simple question of creating a meta-function for each if, and using enable_if for each else branch.

About rlc

Software Analyst in embedded systems and C++, C and VHDL developer, I specialize in security, communications protocols and time synchronization, and am interested in concurrency, generic meta-programming and functional programming and their practical applications. I take a pragmatic approach to project management, focusing on the management of risk and scope. I have over two decades of experience as a software professional and a background in science.
This entry was posted in C & C++, Software Development and tagged , , . Bookmark the permalink.