Crate galil_seiferas [−] [src]

String search in constant space, linear time, for nonorderable alphabets.

In Rust terms this means we can define the function:

fn gs_find<T: Eq>(text: &[T], pattern: &[T]) -> Option<usize> {
    // ...
}

and the function computes in O(n) time and O(1) space. In the worst case, this algorithm makes 4 n character comparisons.

Note that the Crochemore-Perrin (“Two Way” algorithm) is much superior if there is a linear order for the alphabet.

References

Both papers are recommended reading. The comments in this crate’s implementation are also meant to explain and point out important details, so that’s recommended reading too.

[GS] Z. Galil and J. Seiferas, Time-Space-Optimal String Matching, Journal of Computer and System Sciences (1983)
[CR] M. Crochemore and W. Rytter, Squares, Cubes, and Time-Space Efficient String Searching, Algorithmica (1995)

Crate Features

The crate is always no_std

Structs

Pattern

A preprocessed pattern.

Functions

gs_find	This is the Galil-Seiferas string matching algorithm.
gs_find_by	This is the Galil-Seiferas string matching algorithm.