strings/AhoCorasick.cpp

• View this file on GitHub
• Last update: 2024-08-04 10:51:43+00:00

Code

/**
 * Author: Igor Markelov (stole from emaxx-algo)
 * Date: 2022-11-18
 * Description: Build aho-corasick automaton.
 * Time: O(n)
 */

int go(int v, char c);

int get_link(int v) {
    if (t[v].link == -1)
        if (v == 0 || t[v].p == 0)
            t[v].link = 0;
        else
            t[v].link = go(get_link(t[v].p), t[v].pch);
    return t[v].link;
}

int go(int v, char c) {
    if (t[v].go[c] == -1)
        if (t[v].next[c] != -1)
            t[v].go[c] = t[v].next[c];
        else
            t[v].go[c] = v == 0 ? 0 : go(get_link(v), c);
    return t[v].go[c];
}

#line 1 "strings/AhoCorasick.cpp"
/**
 * Author: Igor Markelov (stole from emaxx-algo)
 * Date: 2022-11-18
 * Description: Build aho-corasick automaton.
 * Time: O(n)
 */

int go(int v, char c);

int get_link(int v) {
    if (t[v].link == -1)
        if (v == 0 || t[v].p == 0)
            t[v].link = 0;
        else
            t[v].link = go(get_link(t[v].p), t[v].pch);
    return t[v].link;
}

int go(int v, char c) {
    if (t[v].go[c] == -1)
        if (t[v].next[c] != -1)
            t[v].go[c] = t[v].next[c];
        else
            t[v].go[c] = v == 0 ? 0 : go(get_link(v), c);
    return t[v].go[c];
}

Back to top page