The KMP package

[Tags: bsd3, library]

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.


[Skip to ReadMe]

Properties

Versions0.1, 0.1.0.1, 0.1.0.2
Change logChanges
Dependenciesarray (>=0.3 && <1), base (>=3.0 && <5) [details]
LicenseBSD3
Copyright2012, Cindy Wang (CindyLinz)
AuthorCindy Wang (CindyLinz)
MaintainerCindy Wang <cindylinz@gmail.com>
Stabilityalpha
CategoryAlgorithms
Home pagehttps://github.com/CindyLinz/Haskell-KMP
UploadedMon Mar 5 06:07:18 UTC 2012 by CindyLinz
DistributionsNixOS:0.1.0.2
Downloads681 total (30 in last 30 days)
Votes
0 []
StatusDocs uploaded by user
Build status unknown [no reports yet]

Modules

[Index]

Downloads

Maintainers' corner

For package maintainers and hackage trustees

Readme for KMP-0.1.0.2

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]