Safe Haskell	None
Language	Haskell2010

KMP

Description

Knuth-Morris-Pratt algorithm

A string matching algorithm that generates a prefix function p from an input string s, where p(i) is the length of the longest prefix of s that ends at index i, excluding the prefix [0..i].

Sources:

Synopsis

prefixFunc :: Eq a => Int -> (Int -> a) -> UArray Int Int
prefixFuncBS :: ByteString -> UArray Int Int

Documentation

prefixFunc :: Eq a => Int -> (Int -> a) -> UArray Int Int Source #

Constructs the prefix function. The input sequence should be 0-indexed. O(n).

prefixFuncBS :: ByteString -> UArray Int Int Source #

prefixFunc for a ByteString. O(n).