Алгоритм Ахо-Корасик
Go to file
mingendo e6ca74df53 docs: README 2022-10-15 18:32:43 +04:00
src feat: base implementation 2022-10-15 17:06:18 +04:00
tests feat: base implementation 2022-10-15 17:06:18 +04:00
.gitignore
Cargo.toml feat: base implementation 2022-10-15 17:06:18 +04:00
LICENSE
README.md docs: README 2022-10-15 18:32:43 +04:00

README.md

aho-corasick

The Aho—Korasik algorithm is a substring search algorithm that implements a search for a set of substrings from a dictionary in a given string. The algorithmic complexity of the algorithm is O((n + m) * log k), where n is the total length of all words in the dictionary, k is the size of the alphabet, m is the length of the text.

Usage example:

use aho_corasick::aho_corasick;
use std::collections::BTreeMap;

fn main() {
    let dict = ["aba", "baba", "cc"];
    let text = "ababababa";
    let res = aho_corasick(&dict, text);

    let mut map = BTreeMap::new();
    map.insert(0, vec![0, 2, 4, 6]);
    map.insert(1, vec![1, 3, 5]);
    assert_eq!(map, res);
}

Cargo.toml

[dependencies]
aho-corasick = {git = "https://github.com/mingendo/aho-corasick.git", branch="main"}