fuchsia / third_party / rust-crates / faa85d05aa0269d92a6c69877fb4a50375115349 / . / rustc_deps / vendor / aho-corasick

tree: fd0b7880b918192e668c36dc49dad110eb1edfbe [path history] [tgz]

- .cargo-checksum.json
- .cargo_vcs_info.json
- COPYING
- Cargo.toml
- LICENSE-MIT
- README.md
- UNLICENSE
- benches/
- examples/
- src/

rustc_deps/vendor/aho-corasick/README.md

This crate provides an implementation of the Aho-Corasick algorithm. Its intended use case is for fast substring matching, particularly when matching multiple substrings in a search text. This is achieved by compiling the substrings into a finite state machine.

This implementation provides optimal algorithmic time complexity. Construction of the finite state machine is `O(p)`

where `p`

is the length of the substrings concatenated. Matching against search text is `O(n + p + m)`

, where `n`

is the length of the search text and `m`

is the number of matches.

Dual-licensed under MIT or the UNLICENSE.

https://docs.rs/aho-corasick/.

The documentation contains several examples, and there is a more complete example as a full program in `examples/dict-search.rs`

.

Here is a quick example showing simple substring matching:

use aho_corasick::{Automaton, AcAutomaton, Match}; let aut = AcAutomaton::new(vec!["apple", "maple"]); let mut it = aut.find("I like maple apples."); assert_eq!(it.next(), Some(Match { pati: 1, start: 7, end: 12, })); assert_eq!(it.next(), Some(Match { pati: 0, start: 13, end: 18, })); assert_eq!(it.next(), None);

Aho-Corasick is useful for matching multiple substrings against many long strings. If your long string is fixed, then you might consider building a suffix array of the search text (which takes `O(n)`

time). Matches can then be found in `O(plogn)`

time.