Safe Haskell | Safe |
---|---|

Language | Haskell98 |

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]

## Synopsis

- data Table a
- type MatchState = Int
- build :: Eq a => [a] -> Table a
- matchSingle :: Eq a => Table a -> MatchState -> a -> (Bool, MatchState)
- match :: Eq a => Table a -> [a] -> [Int]

# Documentation

type MatchState = Int Source #

build :: Eq a => [a] -> Table a Source #

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)

matchSingle :: Eq a => Table a -> MatchState -> a -> (Bool, MatchState) Source #

The `matchSingle`

function takes the KMP table, the current state of the matching and the next
element in the sequence and returns whether it finished a matching sequence along with the new
state. This is useful if your input doesn't come in a list or you need other flexibilities.

The matching state is just an integer representing how long of a pattern prefix has been matched already. Therefore the initial state should be 0 if you start with an empty sequence.

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)