code-template/SuffixAutomaton.cpp at master · renamoe/code-template · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
struct SuffixAutomaton {
    struct Node {
        Node *fa;
        Node *ch[Sig];
        int len;
        int pos;
        Node() : fa{}, ch{}, len(0), pos(-1) {}
    };
    std::vector<Node> pool;
    int tot;
    Node *root;

    SuffixAutomaton(const std::string &s) {
        pool.resize(s.length() * 2 + 1);
        tot = 0;
        root = new_node();
        Node *last = root;
        for (int i = 0; i < int(s.length()); ++i) {
            last = extend(last, s[i] - '0', i);
        }
    }
    Node *new_node() {
        return pool.data() + (tot++);
    }
    int id(Node *p) {
        return p - pool.data();
    }
    Node *node(int k) {
        return pool.data() + k;
    }
    Node *extend(Node *p, int c, int pos) {
        Node *np = new_node();
        np->len = p->len + 1;
        np->pos = pos;
        while (p && !p->ch[c]) {
            p->ch[c] = np;
            p = p->fa;
        }
        if (!p) {
            np->fa = root;
        } else {
            Node *q = p->ch[c];
            if (q->len == p->len + 1) {
                np->fa = q;
            } else {
                Node *nq = new_node();
                nq->fa = q->fa;
                std::copy_n(q->ch, Sig, nq->ch);
                nq->len = p->len + 1;
                q->fa = np->fa = nq;
                while (p && p->ch[c] == q) {
                    p->ch[c] = nq;
                    p = p->fa;
                }
            }
        }
        return np;
    }
};