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

Versions 0.1, 0.1.0.1, 0.1.0.2
Dependencies array (>=0.3 && <1), base (>=3.0 && <5) [details]
License BSD3
Copyright 2012, Cindy Wang (CindyLinz)
Author Cindy Wang (CindyLinz)
Maintainer Cindy Wang <cindylinz@gmail.com>
Stability alpha
Category Algorithms
Home page https://github.com/CindyLinz/Haskell-KMP
Uploaded Sun Mar 4 08:08:29 UTC 2012 by CindyLinz
Distributions NixOS:0.1.0.2
Downloads 904 total (10 in the last 30 days)
Votes
0 []
Status Docs uploaded by user
Build status unknown [no reports yet]

Modules

[Index]

Downloads

Maintainer's Corner

For package maintainers and hackage trustees

Readme for KMP

Readme for KMP-0.1.0.1

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]