Safe Haskell | Safe-Infered |
---|
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]
Documentation
build :: Eq a => [a] -> Table aSource
The build
function eats a pattern (list of some Eq) and generates a KMP table.
The time and space complexities are both O(length of the pattern)
match :: Eq a => Table a -> [a] -> [Int]Source
The match
function takes the KMP table and a list to be searched (might be infinite)
and then generates the search results as a list of every matched begining (might be infinite).
The time complexity is O(length of the pattern + length of the searched list)