Suffix Automaton
(String/suffixautomaton.hpp)

• View this file on GitHub
• Last update: 2024-04-26 03:18:17+09:00
• Include: #include "String/suffixautomaton.hpp"

Code

#pragma once

struct SuffixAutomaton {
    struct Node {
        map<char, int> nxt;
        int link, len, origin;
        Node(int L = 0) : link(-1), len(L) {}
    };
    vector<Node> Nodes;
    int last;
    SuffixAutomaton() {
        Nodes.push_back(Node());
        Nodes.back().origin = 0;
        last = 0;
    }
    void push(char c) {
        int nlast = Nodes.size();
        Nodes.push_back(Node(Nodes[last].len + 1));
        Nodes.back().origin = nlast;
        int cur = last;
        while (cur != -1 and !Nodes[cur].nxt.count(c)) {
            Nodes[cur].nxt[c] = nlast;
            cur = Nodes[cur].link;
        }
        if (cur == -1)
            Nodes[nlast].link = 0;
        else {
            int to = Nodes[cur].nxt[c];
            if (Nodes[to].len == Nodes[cur].len + 1)
                Nodes[nlast].link = to;
            else {
                int extra = Nodes.size();
                Nodes.push_back(Nodes[to]);
                Nodes.back().len = Nodes[cur].len + 1;
                Nodes.back().origin = to;
                Nodes[to].link = Nodes[nlast].link = extra;
                while (cur != -1 and Nodes[cur].nxt[c] == to) {
                    Nodes[cur].nxt[c] = extra;
                    cur = Nodes[cur].link;
                }
            }
        }
        last = nlast;
    }
};

/*
 * @brief Suffix Automaton
 */

#line 2 "String/suffixautomaton.hpp"

struct SuffixAutomaton {
    struct Node {
        map<char, int> nxt;
        int link, len, origin;
        Node(int L = 0) : link(-1), len(L) {}
    };
    vector<Node> Nodes;
    int last;
    SuffixAutomaton() {
        Nodes.push_back(Node());
        Nodes.back().origin = 0;
        last = 0;
    }
    void push(char c) {
        int nlast = Nodes.size();
        Nodes.push_back(Node(Nodes[last].len + 1));
        Nodes.back().origin = nlast;
        int cur = last;
        while (cur != -1 and !Nodes[cur].nxt.count(c)) {
            Nodes[cur].nxt[c] = nlast;
            cur = Nodes[cur].link;
        }
        if (cur == -1)
            Nodes[nlast].link = 0;
        else {
            int to = Nodes[cur].nxt[c];
            if (Nodes[to].len == Nodes[cur].len + 1)
                Nodes[nlast].link = to;
            else {
                int extra = Nodes.size();
                Nodes.push_back(Nodes[to]);
                Nodes.back().len = Nodes[cur].len + 1;
                Nodes.back().origin = to;
                Nodes[to].link = Nodes[nlast].link = extra;
                while (cur != -1 and Nodes[cur].nxt[c] == to) {
                    Nodes[cur].nxt[c] = extra;
                    cur = Nodes[cur].link;
                }
            }
        }
        last = nlast;
    }
};

/*
 * @brief Suffix Automaton
 */

Back to top page