hgeometry-combinatorial-0.9.0.0: Data structures, and Data types.

Copyright (C) Frank Staals see the LICENSE file Frank Staals None Haskell2010

Algorithms.StringSearch.KMP

Description

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

Synopsis

# Documentation

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

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

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

Constructs the failure function.

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