KMP implemented on haskell's built-in cons-cell-based lists. http://github.com/mniip/functional-kmp
|Latest on Hackage:||0.1.0.0|
This package is not currently in any snapshots. If you're interested in using it, we recommend adding it to Stackage Nightly. Doing so will make builds more reliable, and allow stackage.org to host generated Haddocks.
A few efficient list-processing functions using the prefix-function, which is defined as:
(prefixFun xs) !! i
is the length of the largest proper substring of
xs ending at position
such that it equals the beginning of
.-----. .-----. a b a c a b a a a b a b a c d 0 0 1 0 1 2 3 1 1 2 3 2 3 4 0 ^
The marked substrings are equal, hence the value at the marked location is their length, 4.