# 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.