functional-kmp: KMP implemented on haskell's built-in cons-cell-based lists.

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 i, such that it equals the beginning of xs.

For example:

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

Modules

[Index]

Downloads

• functional-kmp-0.1.0.0.tar.gz [browse] (Cabal source package)
• Package description (as included in the package)

Maintainer's Corner

Package maintainers

• mniip

For package maintainers and hackage trustees

• edit package information

Candidates

• 0.1.0.0