The KMP package

[ Tags: algorithms, bsd3, library ] [ Propose Tags ]

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
Change log Changes
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>
Category Algorithms
Home page https://github.com/CindyLinz/Haskell-KMP
Uploaded Mon Mar 5 06:07:18 UTC 2012 by CindyLinz
Distributions NixOS:0.1.0.2
Downloads 1119 total (18 in the last 30 days)
Rating (no votes yet) [estimated by rule of succession]
Your Rating
  • λ
  • λ
  • λ
Status Docs uploaded by user
Build status unknown [no reports yet]
Hackage Matrix CI

Modules

[Index]

Downloads

Maintainer's Corner

For package maintainers and hackage trustees


Readme for KMP-0.1.0.2

[back to package description]
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]