#include <algorithm>
#include <cassert>
#include <climits>
#include <deque>
#include <optional>
#include <string>
#include <string_view>
#include <utility>
#include <vector>

namespace bass {

struct TreeVertex {
    int l = 0, r = 0;       // label of the incoming edge: text[l..r)
    int depth = 0;          // |maxstr(v)|
    int terminal = -1;      // suffix ending here, -1 if none
    int sample = -1;        // first occurrence
    int occurrences = 0;    // occurrence of maxstr(v)
    TreeVertex *parent = nullptr, *link = nullptr;
    std::vector<TreeVertex*> children;
    TreeVertex* chain_head = nullptr;
    int pos = 0;
};

// McCreight suffix tree for a byte string.
struct CompactSuffixTree {
    using Vertex = TreeVertex;
    static constexpr int sentinel = 256;

    std::string text;
    std::vector<int> s;
    std::deque<Vertex> memory; // pointers stay valid
    std::vector<Vertex*> suffix_vertex;
    std::vector<Vertex*> vertices;
    std::vector<int> hld_depth;
    std::vector<int> head_pos;
    std::vector<int> parent_pos;
    std::vector<int> suffix_pos;
    bool fast_locate = true;
    Vertex* root = nullptr;

    explicit CompactSuffixTree(std::string text_, bool fast_locate_ = true)
        : text(std::move(text_)), fast_locate(fast_locate_) {
        assert(text.size() < static_cast<std::size_t>(INT_MAX));
        build();
    }

    CompactSuffixTree(const CompactSuffixTree&) = delete;
    CompactSuffixTree& operator=(const CompactSuffixTree&) = delete;

    Vertex* make(Vertex* parent, int l, int r, int depth) {
        memory.push_back({});
        Vertex* v = &memory.back();
        v->parent = parent;
        v->l = l;
        v->r = r;
        v->depth = depth;
        return v;
    }

    Vertex* child(Vertex* v, int c) const {
        for (Vertex* u : v->children) {
            if (s[u->l] == c) {
                return u;
            }
        }
        return nullptr;
    }

    static int edge_length(Vertex* v) {
        return v->r - v->l;
    }

    Vertex* split(Vertex* v, int length) {
        assert(0 < length && length < edge_length(v));
        Vertex* p = v->parent;
        Vertex* middle = make(p, v->l, v->l + length, p->depth + length);

        auto place = std::find(p->children.begin(), p->children.end(), v);
        assert(place != p->children.end());
        *place = middle;

        v->parent = middle;
        v->l += length;
        middle->children.push_back(v);
        return middle;
    }

    // Finds the suffix link by skipping complete edges.
    Vertex* fast_scan(Vertex* v) {
        if (v == root) {
            return root;
        }
        if (v->link != nullptr) {
            return v->link;
        }

        Vertex* p = v->parent;
        Vertex* cur;
        int l = v->l;
        int left = edge_length(v);
        if (p == root) {
            cur = root;
            ++l;
            --left;
        } else {
            assert(p->link != nullptr);
            cur = p->link;
        }

        while (left > 0) {
            Vertex* u = child(cur, s[l]);
            assert(u != nullptr);
            int len = edge_length(u);
            if (left < len) {
                cur = split(u, left);
                left = 0;
            } else {
                cur = u;
                l += len;
                left -= len;
            }
        }
        return v->link = cur;
    }

    // Compares only the not-yet-known part of suffix start.
    Vertex* slow_scan(Vertex* v, int start) {
        int n = static_cast<int>(s.size());
        while (true) {
            int pos = start + v->depth;
            assert(pos < n);
            Vertex* u = child(v, s[pos]);
            if (u == nullptr) {
                return v;
            }

            int matched = 0;
            while (matched < edge_length(u) && pos + matched < n
                   && s[u->l + matched] == s[pos + matched]) {
                ++matched;
            }
            if (matched < edge_length(u)) {
                return split(u, matched);
            }
            v = u;
        }
    }

    void add_suffix(Vertex* p, int start) {
        int n = static_cast<int>(s.size());
        int l = start + p->depth;
        assert(l < n && child(p, s[l]) == nullptr);
        Vertex* leaf = make(p, l, n, n - start);
        p->children.push_back(leaf);
        suffix_vertex[start] = leaf;
    }

    static void erase_child(Vertex* p, Vertex* v) {
        auto it = std::find(p->children.begin(), p->children.end(), v);
        assert(it != p->children.end());
        p->children.erase(it);
    }

    // Removes the auxiliary sentinel. Suffix endpoints remain explicit.
    void remove_sentinel() {
        int n = static_cast<int>(text.size());
        for (int start = 0; start <= n; ++start) {
            Vertex* leaf = suffix_vertex[start];
            Vertex* p = leaf->parent;
            if (start == n) {
                erase_child(p, leaf);
            } else if (edge_length(leaf) == 1) {
                erase_child(p, leaf);
                assert(p->depth == n - start);
                p->terminal = start;
                suffix_vertex[start] = p;
            } else {
                --leaf->r;
                --leaf->depth;
                leaf->terminal = start;
            }
        }
        suffix_vertex.resize(n);
    }

    void prepare_locate() {
        vertices = {root};
        for (std::size_t i = 0; i < vertices.size(); ++i) {
            for (Vertex* u : vertices[i]->children) {
                vertices.push_back(u);
            }
        }

        for (std::size_t i = vertices.size(); i-- > 0;) {
            Vertex* v = vertices[i];
            v->occurrences = (v->terminal != -1);
            v->sample = v->terminal;
            int sz = 1;
            for (Vertex* u : v->children) {
                v->occurrences += u->occurrences;
                if (v->sample == -1 || u->sample < v->sample) {
                    v->sample = u->sample;
                }
                sz += u->pos;
            }
            v->pos = sz; // temporary subtree size if fast_locate
        }

        if (!fast_locate) {
            // Keep DFS order in vertices; pos unused for locate.
            return;
        }

        auto heavy = [](Vertex* v) -> Vertex* {
            Vertex* h = nullptr;
            int best = 0;
            for (Vertex* u : v->children) {
                if (u->pos > best) {
                    best = u->pos;
                    h = u;
                }
            }
            return h;
        };

        std::vector<Vertex*> order = std::move(vertices);
        vertices.clear();
        vertices.reserve(order.size());
        std::vector<std::pair<Vertex*, Vertex*>> stack = {{root, root}};
        while (!stack.empty()) {
            auto [v, head] = stack.back();
            stack.pop_back();
            while (v != nullptr) {
                v->chain_head = head;
                v->pos = static_cast<int>(vertices.size());
                vertices.push_back(v);
                Vertex* h = heavy(v);
                for (Vertex* u : v->children) {
                    if (u != h) {
                        stack.emplace_back(u, u);
                    }
                }
                v = h;
            }
        }

        const int n = static_cast<int>(vertices.size());
        hld_depth.resize(n);
        head_pos.resize(n);
        parent_pos.resize(n);
        for (int i = 0; i < n; ++i) {
            Vertex* v = vertices[i];
            hld_depth[i] = v->depth;
            head_pos[i] = v->chain_head->pos;
            parent_pos[i] = v->parent ? v->parent->pos : -1;
        }
        suffix_pos.resize(text.size());
        for (std::size_t i = 0; i < text.size(); ++i) {
            suffix_pos[i] = suffix_vertex[i]->pos;
        }
    }

    void build() {
        for (char c : text) {
            s.push_back(static_cast<unsigned char>(c));
        }
        s.push_back(sentinel);

        suffix_vertex.resize(s.size());
        root = make(nullptr, 0, 0, 0);
        root->link = root;

        Vertex* previous_head = root;
        for (int start = 0; start < static_cast<int>(s.size()); ++start) {
            Vertex* head = slow_scan(fast_scan(previous_head), start);
            add_suffix(head, start);
            previous_head = head;
        }
        remove_sentinel();
        prepare_locate();
    }

    // HLD index of the vertex recognizing text[start..start+length).
    int locate_id(int start, int length) const {
        assert(fast_locate);
        if (length == 0) {
            return root->pos;
        }
        int v = suffix_pos[start];
        while (true) {
            const int head = head_pos[v];
            const int before = parent_pos[head];
            if (before < 0 || hld_depth[before] < length) {
                // Fast path: depths increase by 1 along the HLD chain.
                if (hld_depth[v] - hld_depth[head] == v - head) {
                    if (hld_depth[head] >= length) {
                        return head;
                    }
                    return head + (length - hld_depth[head]);
                }
                int L = head;
                int R = v;
                while (L < R) {
                    const int M = (L + R) >> 1;
                    if (hld_depth[M] < length) {
                        L = M + 1;
                    } else {
                        R = M;
                    }
                }
                return L;
            }
            v = before;
        }
    }

    Vertex* locate_suffix(int start, int length) const {
        assert(0 <= start && start <= static_cast<int>(text.size()));
        assert(0 <= length
               && length <= static_cast<int>(text.size()) - start);
        if (fast_locate) {
            return vertices[locate_id(start, length)];
        }
        if (length == 0) {
            return root;
        }
        Vertex* v = suffix_vertex[start];
        while (v->parent != nullptr && v->parent->depth >= length) {
            v = v->parent;
        }
        return v;
    }

    // Returns the leftmost occurrence of an arbitrary string.
    std::optional<int> find(std::string_view pattern) const {
        if (pattern.empty()) {
            return 0;
        }

        Vertex* v = root;
        std::size_t pos = 0;
        while (pos < pattern.size()) {
            Vertex* u = child(
                v, static_cast<unsigned char>(pattern[pos]));
            if (u == nullptr) {
                return std::nullopt;
            }

            for (int i = u->l; i < u->r && pos < pattern.size(); ++i, ++pos) {
                if (s[i] != static_cast<unsigned char>(pattern[pos])) {
                    return std::nullopt;
                }
            }
            v = u;
        }
        return v->sample;
    }

    std::string_view max_string(const Vertex* v) const {
        return v == root ? std::string_view{}
                         : std::string_view(text).substr(v->sample, v->depth);
    }
};

enum class TreeKind { Pre, Suf };

// All coordinates are zero-based half-open intervals [l, r).
struct PreSufTrees {
    std::string text;
    CompactSuffixTree pre, suf;

    static std::string reversed(const std::string& s) {
        return {s.rbegin(), s.rend()};
    }

    explicit PreSufTrees(std::string text_)
        : text(std::move(text_)),
          pre(text, true),
          suf(reversed(text), true) {}

    TreeVertex* locate(TreeKind kind, int l, int r) const {
        assert(0 <= l && l <= r && r <= static_cast<int>(text.size()));
        return kind == TreeKind::Pre
            ? pre.locate_suffix(l, r - l)
            : suf.locate_suffix(static_cast<int>(text.size()) - r, r - l);
    }

    TreeVertex* locate_pre(int l, int r) const {
        return locate(TreeKind::Pre, l, r);
    }

    TreeVertex* locate_suf(int l, int r) const {
        return locate(TreeKind::Suf, l, r);
    }

    std::optional<int> find(std::string_view pattern) const {
        return pre.find(pattern);
    }
};

} // namespace bass