hgeometry-combinatorial-0.12.0.1: Data structures, and Data types.
Copyright(C) Frank Staals
Licensesee the LICENSE file
MaintainerFrank Staals
Safe HaskellNone
LanguageHaskell2010

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