### 30 releases

new 0.6.10 | Feb 16, 2019 |
---|---|

0.6.9 | Oct 29, 2018 |

0.6.8 | Aug 27, 2018 |

0.6.6 | Jul 12, 2018 |

0.3.0 | Jul 14, 2015 |

#**2** in Text processing

**323,926** downloads per month

Used in **4,152** crates (12 directly)

**Unlicense/MIT**

61KB

1.5K
SLoC

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

where `O (p)`

`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.

### Documentation

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

### Example

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``)``;`

### Alternatives

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

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

`O``(`p `log``(`n`)``)`

time.#### Dependencies

~93KB