Algorithms.StringSearch.KMP

Implementation of Knuth-Morris-Pratt String-searching algorithm. The exposition is based on that of Goodrich and Tamassia in "Data Structures and Algorithms in Java 2nd Edition".

Documentation

isSubStringOf :: (Eq a, Foldable p, Foldable t) => p a -> t a -> Maybe Int

Test if the first argument, the pattern p, occurs as a consecutive subsequence in t.

running time: \(O(n+m)\), where p has length \(m\) and t has length \(n\).

kmpMatch :: Eq a => Vector a -> Vector a -> Maybe Int

Test if the first argument, the pattern p, occurs as a consecutive subsequence in t.

running time: \(O(n+m)\), where p has length \(m\) and t has length \(n\).

buildFailureFunction :: forall a. Eq a => Vector a -> Vector Int

Constructs the failure function.

running time: \(O(m)\).