naive_opt

The optimized naive string-search algorithm.

Features

• The naive string-searching algorithm
• Enhanced with 1-byte search like the libc++ and the libstd++ string::find
• Specializing in UTF-8 strings, which is a feature of rust
• The ASCII Stochastics search
• Support the zero overhead trait.
• minimum support: rustc 1.41.1 (f3e1a954d 2020-02-24)

Compatibility

This crate is implemented to replace the rust std library. However, the method names are different, so please rewrite your code. It shouldn't be too difficult.

compatibility:

| rust std::str | this crate | |:-----------------------------|:---------------------------------------| | std::str::find() | naive_opt::Search::search() | | std::str::rfind() | naive_opt::Search::rsearch() | | std::str::contains() | naive_opt::Search::includes() | | std::str::match_indices() | naive_opt::Search::search_indices() | | std::str::rmatch_indices() | naive_opt::Search::rsearch_indices() |

Examples

Example function:

```rust use naiveopt::{stringsearch, stringrsearch}; use naiveopt::{stringsearchindices, stringrsearchindices};

let haystack = "111 a 111b"; let needle = "a"; let r = stringsearch(haystack, needle); asserteq!(r, Some(4));

asserteq!(stringsearch(haystack, "1"), Some(0)); asserteq!(stringrsearch(haystack, "1"), Some(8));

let v: Vec<_> = stringsearchindices("abc345abc901abc", "abc").collect(); asserteq!(v, [(0, "abc"), (6, "abc"), (12, "abc")]); let v: Vec<_> = stringrsearchindices("abc345abc901abc", "abc").collect(); asserteq!(v, [(12, "abc"), (6, "abc"), (0, "abc")]); ```

Example trait: Search

```rust use naive_opt::Search;

let haystack = "111 a 111b"; let needle = "a"; let r = haystack.search(needle); assert_eq!(r, Some(4));

asserteq!(haystack.search("1"), Some(0)); asserteq!(haystack.rsearch("1"), Some(8));

let v: Vec<_> = "abc345abc901abc".searchindices("abc").collect(); asserteq!(v, [(0, "abc"), (6, "abc"), (12, "abc")]); let v: Vec<_> = "abc345abc901abc".rsearchindices("abc").collect(); asserteq!(v, [(12, "abc"), (6, "abc"), (0, "abc")]); ```

Example trait: SearchIn

```rust use naive_opt::SearchIn;

let haystack = "111 a 111b"; let needle = "a"; let r = needle.searchin(haystack); asserteq!(r, Some(4));

asserteq!("1".searchin(haystack), Some(0)); asserteq!("1".rsearchin(haystack), Some(8)); ```

Benchmark results

• compile by rustc 1.53.0 (53cb7b09b 2021-06-17)

| name | bench:en | bench:ja | musl:en | musl:ja | |:------------------------|------------:|------------:|------------:|------------:| | stdstrstr | 597.500 uc | 486.830 uc | 612.780 uc | 494.020 uc | | stdstringstring | 596.120 uc | 484.470 uc | 621.090 uc | 521.630 uc | | funcstrstr | 92.700 uc | 111.850 uc | 91.712 uc | 113.740 uc | | funcstringstring | 92.046 uc | 111.630 uc | 91.629 uc | 114.720 uc | | traitstrstr | 86.913 uc | 107.620 uc | 86.574 uc | 108.830 uc | | traitstringstring | 86.268 uc | 107.420 uc | 87.603 uc | 107.440 uc | | stdindices | 537.580 uc | 403.150 uc | 530.250 uc | 405.990 uc | | funcindices | 87.310 uc | 108.470 uc | 87.587 uc | 109.770 uc | | trait_indices | 87.383 uc | 107.750 uc | 87.895 uc | 109.070 uc |

• std is std::str::find()
• us is micro seconds
• :en is english haystack.
• :ja is japanese haystack.
• musl is x86_64-unknown-linux-musl
• bench on intel Q6600 @ 2.40GHz

Changelogs

This crate's changelog here.

References

• my research: string searching algorithm
• my research: string find
• wikipedia: string searching algprithm
• memx - rust crate for the fast mem lib

License

This project is licensed under either of

• Apache License, Version 2.0, (LICENSE-APACHE or https://www.apache.org/licenses/LICENSE-2.0)
• MIT license (LICENSE-MIT or https://opensource.org/licenses/MIT)

at your option.