Knuth–Morris–Pratt string searching algorithm

Latest on Hackage:

This package is not currently in any snapshots. If you're interested in using it, we recommend adding it to Stackage Nightly. Doing so will make builds more reliable, and allow to host generated Haddocks.

BSD3 licensed by Cindy Wang (CindyLinz)
Maintained by Cindy Wang
This module implements the Knuth-Morris-Pratt algorithm.
It can search a word in a text in O(m+n) time, where m and n are the length of the word and the text.

This module can apply on any list of instance of Eq.

Donald Knuth; James H. Morris, Jr, Vaughan Pratt (1977).
Fast pattern matching in strings.
SIAM Journal on Computing 6 (2): 323–350. doi:10.1137/0206024

Sample usage:

> let
> word = "abababcaba"
> text = "abababababcabababcababbb"
> kmpTable = build word
> result = match kmpTable text
> -- the 'result' should be [4, 11]

Changes 2012.3.5
Reimplement the real KMP version, instead of the MP version.
Thank MaskRay from #haskell for noticing. 2012.3.4
Haddock fix

0.1 2012.3.2
First version
Depends on:
Used by 2 packages:
comments powered byDisqus