KMP: Knuth–Morris–Pratt string searching algorithm

[ algorithms, bsd3, library ] [ Propose Tags ] [ Report a vulnerability ]

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]

Modules

[Index] [Quick Jump]

Data
- Algorithms
  - Data.Algorithms.KMP

Downloads

KMP-0.2.0.0.tar.gz [browse] (Cabal source package)
Package description (as included in the package)

Maintainer's Corner

Package maintainers

CindyLinz

For package maintainers and hackage trustees

edit package information

Candidates

No Candidates

Versions [RSS]	0.1, 0.1.0.1, 0.1.0.2, 0.2.0.0
Change log	Changes
Dependencies	array (>=0.3 && <1), base (>=3.0 && <5) [details]
Tested with	ghc ==7.0.4
License	BSD-3-Clause
Copyright	2012-2018, Cindy Wang (CindyLinz)
Author	Cindy Wang (CindyLinz) Silvan Mosberger (Infinisil@github)
Maintainer	Cindy Wang <cindylinz@gmail.com>
Category	Algorithms
Home page	https://github.com/CindyLinz/Haskell-KMP
Uploaded	by CindyLinz at 2018-12-17T06:36:28Z
Distributions	NixOS:0.2.0.0
Reverse Dependencies	2 direct, 0 indirect [details]
Downloads	4158 total (8 in the last 30 days)
Rating	(no votes yet) [estimated by Bayesian average]
Your Rating	λ λ λ
Status	Docs available [build log] Last success reported on 2018-12-17 [all 1 reports]

Readme for KMP-0.2.0.0

[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]