Copyright	(C) Frank Staals
License	see the LICENSE file
Maintainer	Frank Staals
Safe Haskell	None
Language	GHC2021

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

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

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 :: Eq a => Vector a -> Vector Int Source #

Constructs the failure function.

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