Module texcraft_stdext::algorithms::substringsearch
source · Expand description
Knuth–Morris–Pratt substring search algorithm
This module contains an optimal in time algorithm for finding a substring in a string. By ‘string’ and ‘substring’ we mean a vector of elements of the same type. The algorithm is due to Knuth, Morris and Pratt.
The API for this module is based on two assumptions:
-
There may be multiple searches for the same substring in different strings.
-
The elements of the string may be generated on the demand as the search progresses. That is, the full string is not necessarily known at the start.
Example
To use the algorithm, a Matcher is first created. This factory takes ownership of the substring. On initialization the matcher computes a number of internal quantities which make the subsequent matching fast. These quantities depend on the substring, so mutating the substring after it has been passed to the matcher is statically prevented.
To match a string, a new Search instance is created by calling Matcher::start. Elements
of the string are passed in one at a time to the next method
of the matcher.
If the substring has length m and matches the last m elements that
have been passed in, the next method returns true.
Otherwise it returns false.
The matcher may be used to find multiple instances of the substring
in the same string.
let substring = nevec![2, 3, 2];
let matcher = Matcher::new(substring);
let mut search = matcher.start();
assert_eq![search.next(&1), false];
assert_eq![search.next(&2), false];
assert_eq![search.next(&3), false];
assert_eq![search.next(&2), true];
assert_eq![search.next(&3), false];
assert_eq![search.next(&2), true];Structs
- Data structure used to match a specific substring in many strings.
- Data structure used to search for specific substring within a specific string.