KMP: Knuth–Morris–Pratt string searching algorithm

[ 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]
Versions [faq] 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]
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 Mon Dec 17 06:36:28 UTC 2018
Distributions NixOS:0.2.0.0
Downloads 2232 total (40 in the last 30 days)
Rating (no votes yet) [estimated by rule of succession]
Your Rating
  • λ
  • λ
  • λ
Status Hackage Matrix CI
Docs available [build log]
Last success reported on 2018-12-17 [all 1 reports]

Modules

[Index] [Quick Jump]

Downloads

Maintainer's Corner

For package maintainers and hackage trustees


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]