#string #substring #search #pattern #no-std

no-std galil-seiferas

General string search in constant space, linear time, for nonorderable alphabets

6 releases

Uses old Rust 2015

0.1.5 Nov 25, 2017
0.1.4 Nov 21, 2017

#4 in #substring-search

Download history 63/week @ 2022-06-12 61/week @ 2022-06-19 63/week @ 2022-06-26 67/week @ 2022-07-03 64/week @ 2022-07-10 62/week @ 2022-07-17 71/week @ 2022-07-24 57/week @ 2022-07-31 79/week @ 2022-08-07 74/week @ 2022-08-14 68/week @ 2022-08-21 59/week @ 2022-08-28 82/week @ 2022-09-04 77/week @ 2022-09-11 70/week @ 2022-09-18 62/week @ 2022-09-25

304 downloads per month
Used in 3 crates

MIT/Apache

37KB
714 lines

General string search in constant space, linear time, for nonorderable alphabets. Also known as exact string matching.

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.

This work is Copyright 2017 by Ulrik Sverdrup "bluss"; see license terms in the package.

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)

Dependencies

~22KB