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 ++ ) (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