#string #search #text #aho #corasick

bin+lib aho-corasick

Fast multiple substring searching with finite state machines

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

Download history 62313/week @ 2018-09-14 67415/week @ 2018-09-21 63091/week @ 2018-09-28 66896/week @ 2018-10-05 65238/week @ 2018-10-12 69456/week @ 2018-10-19 63347/week @ 2018-10-26 80926/week @ 2018-11-02 80350/week @ 2018-11-09 79150/week @ 2018-11-16 67094/week @ 2018-11-23 69019/week @ 2018-11-30 65086/week @ 2018-12-07

232,009 downloads per month
Used in 3,707 crates (11 directly)


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.

Build status

Dual-licensed under MIT or the UNLICENSE.




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.