### 28 releases

0.6.8 | Aug 27, 2018 |
---|---|

0.6.6 | Jul 12, 2018 |

0.6.4 | Nov 30, 2017 |

0.6.3 | Mar 17, 2017 |

0.3.0 | Jul 14, 2015 |

#**3** in Text processing

**232,009** downloads per month

Used in **3,343** crates (11 directly)

**Unlicense/MIT**

60KB

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

### 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 `O(n)`

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

time.

#### Dependencies

~265KB

- memchr 2.0

- dev csv 1.0
- dev docopt 1.0
- dev memmap 0.6
- dev quickcheck 0.7
- dev rand 0.5
- dev serde 1.0
- dev serde_derive 1.0