CP-Algorithms Library

This documentation is automatically generated by competitive-verifier/competitive-verifier

View the Project on GitHub cp-algorithms/cp-algorithms-aux

:heavy_check_mark: cp-algo/structures/suffix_automaton.hpp

Depends on

Required by

Verified with

Code

#ifndef CP_ALGO_STRUCTURES_SUFFIX_AUTOMATON_HPP
#define CP_ALGO_STRUCTURES_SUFFIX_AUTOMATON_HPP
#include <algorithm>
#include <array>
#include <bit>
#include <cassert>
#include <cstdint>
#include <cstdlib>
#include <cstring>
#include <limits>
#include <memory>
#include <new>
#include <string>
#include <string_view>
#include <utility>
#include <vector>
#include "../util/big_alloc.hpp"
#include "../util/checkpoint.hpp"

namespace cp_algo::structures {
    auto suffix_array(std::string text);

    // An immutable substring index for lowercase Latin letters.
    // Packed state IDs support strings of fewer than 2^23 characters.
    class suffix_automaton {
    public:
        explicit suffix_automaton(std::string text): suffix_automaton(std::move(text), false) {}

        int64_t count_distinct() const { return distinct; }

        // Half-open intervals [a,b) in the indexed text and [c,d) in other.
        std::array<int, 4> longest_common_substring(std::string_view other) const {
            switch(width) {
                case 0: return match<0>(other);
                case 1: return match<1>(other);
                case 2: return match<2>(other);
                case 4: return match<4>(other);
                default: return match<-1>(other);
            }
        }

    private:
        friend auto suffix_array(std::string text);
        // Align large mappings to huge-page boundaries. This policy is local to SAM.
        template<class T> struct page_allocator {
            using value_type = T;
            template<class U> struct rebind { using other = page_allocator<U>; };
            page_allocator() = default;
            template<class U> page_allocator(page_allocator<U> const&) {}
            bool operator==(page_allocator const&) const { return true; }
            static constexpr size_t page = 1U << 21, threshold = 1U << 20;
            T* allocate(size_t count) {
                if(count > (std::numeric_limits<size_t>::max() - 2 * page) / sizeof(T))
                    throw std::bad_array_new_length();
                size_t bytes = count * sizeof(T);
#ifdef __linux__
                if(bytes >= threshold) {
                    bytes = (bytes + page - 1) & -page;
                    void *raw = mmap(nullptr, bytes + page, PROT_READ | PROT_WRITE,
                                     MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
                    if(raw == MAP_FAILED) throw std::bad_alloc();
                    uintptr_t begin = (uintptr_t(raw) + page - 1) & -page;
                    size_t before = begin - uintptr_t(raw), after = page - before;
                    if(before) munmap(raw, before);
                    if(after) munmap(reinterpret_cast<void*>(begin + bytes), after);
                    madvise(reinterpret_cast<void*>(begin), bytes, MADV_HUGEPAGE);
                    return reinterpret_cast<T*>(begin);
                }
#endif
                auto p = static_cast<T*>(std::calloc(std::max(count, size_t(1)), sizeof(T)));
                if(!p) throw std::bad_alloc();
                return p;
            }
            void deallocate(T *p, size_t count) {
#ifdef __linux__
                if(count * sizeof(T) >= threshold) {
                    munmap(p, (count * sizeof(T) + page - 1) & -page);
                    return;
                }
#endif
                std::free(p);
            }
        };
        template<class T> using storage = std::vector<T, page_allocator<T>>;
        using row = std::array<int, 26>;
        // Newly mapped pages are zero. Begin row lifetimes without touching every page.
        template<class T> struct zero_storage {
            T *data = nullptr;
            size_t capacity = 0;
            zero_storage() = default;
            explicit zero_storage(size_t n): data(page_allocator<T>{}.allocate(n)), capacity(n) {
                std::uninitialized_default_construct_n(data, n);
            }
            zero_storage(zero_storage const &other): zero_storage(other.capacity) {
                if(capacity) std::copy_n(other.data, capacity, data);
            }
            zero_storage(zero_storage &&other) noexcept { swap(other); }
            zero_storage &operator=(zero_storage other) noexcept { swap(other); return *this; }
            void swap(zero_storage &other) noexcept {
                std::swap(data, other.data); std::swap(capacity, other.capacity);
            }
            ~zero_storage() { if(data) page_allocator<T>{}.deallocate(data, capacity); }
        };
        struct clone_data { int len, pos; };
        struct transitions { uint32_t a = 0, b = 0; };
        static constexpr uint32_t dense_tag = 0x80000000, id_mask = 0xFFFFFF;
        std::string word;
        int n = 0, alphabet = 26, width = 0;
        int64_t distinct = 0;
        std::array<int, 26> code{};
        storage<clone_data> clones;
        storage<int> link, flat;
        storage<transitions> to;
        storage<row> dense;
        zero_storage<row> clone_edges, prefix_edges;
        int prefix_bound = 0;

        suffix_automaton(std::string text, bool suffix_order): word(std::move(text)) {
            assert(word.size() < (1U << 23));
            n = (int)word.size();
            if(suffix_order) {
                for(int c = 0; c < 26; c++) code[c] = c;
            } else {
                code.fill(-1);
                uint32_t letters = 0;
                for(unsigned char c: word) {
                    assert(c >= 'a' && c <= 'z');
                    letters |= 1U << (c - 'a');
                }
                alphabet = 0;
                for(int c = 0; c < 26; c++) {
                    if(letters >> c & 1) code[c] = alphabet++;
                }
                if(alphabet != 26) {
                    for(char &c: word) c = char('a' + code[c - 'a']);
                }
                if(alphabet <= 1) width = 1;
                else if(alphabet <= 2) width = 2;
                else if(alphabet <= 4) width = 4;
                // Avoid tagged lookups while the ordinary dense rows fit in 32 MiB.
                else if(alphabet <= 16 || size_t(n) * alphabet <= (1U << 23)) width = -1;
            }
            clones.reserve(n);
            link.resize(2 * n + 1);
            if(suffix_order) {
                prefix_edges = zero_storage<row>(n + 1);
                clone_edges = zero_storage<row>(n);
            } else if(width == 0) {
                // At most one dense row per state, including clones.
                dense.reserve(link.size());
                to.reserve(link.size());
                to.resize(n + 1);
            } else {
                flat.resize(link.size() * (width > 0 ? width : alphabet));
            }
            checkpoint("init");
            if(suffix_order) {
                build<0, false, true>();
            }
            else switch(width) {
                case 0: build<0>(); break;
                case 1: build<1>(); break;
                case 2: build<2>(); break;
                case 4: build<4>(); break;
                default: build<-1>();
            }
            checkpoint("build");
        }

        int states() const { return n + 1 + (int)clones.size(); }
        // Ordinary state i represents prefix i; only clones need stored metadata.
        int length(int v) const { return v <= n ? v : clones[v - n - 1].len; }
        int position(int v) const { return v <= n ? v : clones[v - n - 1].pos; }

        static row &clone_row(int p, uintptr_t base) {
            return *reinterpret_cast<row*>(base + size_t(p) * sizeof(row));
        }
        template<int Width, bool CloneDense = false>
        int get(int p, int x, uintptr_t clone_base = 0) const {
            if constexpr(CloneDense) {
                if(p > n) return clone_row(p, clone_base)[x];
                // A prefix state's first edge is always p -> p+1 and never redirected.
                if(word[p] == char('a' + x)) return p + 1;
                return p <= prefix_bound ? prefix_edges.data[p][x] : 0;
            }
            if constexpr(Width != 0) {
                return flat[size_t(p) * (Width > 0 ? Width : alphabet) + x];
            } else {
                auto t = to[p];
                if(t.a & dense_tag) return dense[t.a & ~dense_tag][x];
                if((t.a >> 24) == unsigned(x + 1)) return int(t.a & id_mask);
                if((t.b >> 24) == unsigned(x + 1)) return int(t.b & id_mask);
                return 0;
            }
        }
        template<int Width, bool CloneDense = false>
        void set(int p, int x, int v, uintptr_t clone_base = 0) {
            if constexpr(CloneDense) {
                if(p > n) { clone_row(p, clone_base)[x] = v; return; }
                prefix_bound = std::max(prefix_bound, p);
                prefix_edges.data[p][x] = v;
                return;
            }
            if constexpr(Width != 0) {
                flat[size_t(p) * (Width > 0 ? Width : alphabet) + x] = v;
            } else {
                auto &t = to[p];
                auto encoded = (uint32_t(x + 1) << 24) | v;
                if(t.a & dense_tag) dense[t.a & ~dense_tag][x] = v;
                else if(!t.a || (t.a >> 24) == unsigned(x + 1)) t.a = encoded;
                else if(!t.b || (t.b >> 24) == unsigned(x + 1)) t.b = encoded;
                else {
                    std::array<int, 26> row{};
                    row[(t.a >> 24) - 1] = t.a & id_mask;
                    row[(t.b >> 24) - 1] = t.b & id_mask;
                    row[x] = v;
                    t.a = dense_tag | uint32_t(dense.size());
                    dense.push_back(row);
                }
            }
        }
        // In suffix-order mode the high byte caches immutable clone lengths.
        // Zero denotes an ordinary state; 255 falls back to full metadata.
        int tagged_length(uint32_t v) const {
            int len = v >> 24;
            return len == 255 ? length(v & id_mask) : len ? len : int(v & id_mask);
        }
        template<int Width, bool Count = true, bool CloneDense = false>
        void build() {
            auto state_id = [](uint32_t v) -> int {
                if constexpr(CloneDense) return v & id_mask;
                else return v;
            };
            auto state_length = [&](uint32_t v) {
                if constexpr(CloneDense) return tagged_length(v);
                else return length(v);
            };
            // Compute the ID-to-row adjustment once, outside the lookup dependency chain.
            uintptr_t clone_base = 0;
            if constexpr(CloneDense)
                clone_base = reinterpret_cast<uintptr_t>(clone_edges.data) - size_t(n + 1) * sizeof(row);
            int last = 0;
            for(unsigned char c: word) {
                int x = c - 'a';
                uint32_t current = last;
                if constexpr(CloneDense) {
                    // The first edge of the newest prefix is implicit.
                    current = link[last];
                }
                int p = state_id(current);
                ++last;
                uint32_t found;
                while(!(found = get<Width, CloneDense>(p, x, clone_base))) {
                    set<Width, CloneDense>(p, x, last, clone_base);
                    current = link[p];
                    p = state_id(current);
                }
                int q = state_id(found);
                if(q != last) {
                    int len = state_length(current) + 1;
                    if(state_length(found) == len) link[last] = found;
                    else {
                        int clone = states();
                        clones.push_back({len, position(q)});
                        if constexpr(CloneDense) {
                            auto &copy = clone_row(clone, clone_base);
                            if(q > n) copy = clone_row(q, clone_base);
                            else {
                                if(q <= prefix_bound) copy = prefix_edges.data[q];
                                copy[word[q] - 'a'] = q + 1;
                            }
                        } else if constexpr(Width != 0) {
                            int stride = Width > 0 ? Width : alphabet;
                            std::copy_n(flat.data() + size_t(q) * stride, stride,
                                        flat.data() + size_t(clone) * stride);
                        } else {
                            auto row = to[q];
                            if(row.a & dense_tag) {
                                auto copy = dense[row.a & ~dense_tag];
                                row.a = dense_tag | uint32_t(dense.size());
                                dense.push_back(copy);
                            }
                            to.push_back(row);
                        }
                        uint32_t tagged = clone;
                        if constexpr(CloneDense) tagged |= uint32_t(std::min(len, 255)) << 24;
                        link[last] = link[q] = tagged;
                        uint32_t next;
                        while(state_id(next = get<Width, CloneDense>(p, x, clone_base)) == q) {
                            set<Width, CloneDense>(p, x, tagged, clone_base);
                            current = link[p];
                            p = state_id(current);
                        }
                        // The first different end-position class is the clone's suffix link.
                        // Redirecting at the root makes that final transition the clone itself.
                        link[clone] = state_id(next) == clone ? 0 : next;
                    }
                }
                if constexpr(Count) distinct += last - length(link[last]);
            }
        }
        template<int Width>
        std::array<int, 4> match(std::string_view other) const {
            int v = 0, matched = 0, best = 0, end_s = 0, end_t = 0;
            for(int i = 0; i < (int)other.size(); i++) {
                unsigned c = (unsigned char)other[i] - unsigned('a');
                int x = c < 26 ? code[c] : -1;
                if(x < 0) { v = matched = 0; continue; }
                while(v && !get<Width>(v, x)) {
                    v = link[v];
                    matched = length(v);
                }
                v = get<Width>(v, x);
                matched = v ? matched + 1 : 0;
                if(matched > best) { best = matched; end_s = position(v); end_t = i + 1; }
            }
            checkpoint("query");
            return {end_s - best, end_s, end_t - best, end_t};
        }

        // Consumes a temporary SAM of the reversed input. No storage mutation is public.
        [[gnu::always_inline]] auto take_suffix_order() && {
            dense = decltype(dense){};
            clone_edges = zero_storage<row>{};
            prefix_edges = zero_storage<row>{};
            int size = states();
            const int n = this->n;
            auto links = link.data();
            auto text = word.data();
            auto clone = clones.data();
            auto position = [&](int v) { return v <= n ? v : clone[v - n - 1].pos; };
            auto tagged_length = [&](uint32_t v) {
                int len = v >> 24;
                return len == 255 ? (int(v & id_mask) <= n ? int(v & id_mask) : clone[(v & id_mask) - n - 1].len)
                                  : len ? len : int(v & id_mask);
            };
            struct tree_node { uint32_t offset, mask; };
            zero_storage<tree_node> tree(size + 1);
            zero_storage<int> children(size);
            uint32_t border = links[n];
            while((border & id_mask) > unsigned(n) && tagged_length(border) > prefix_bound)
                border = links[border & id_mask];
            int last_branch = std::max(prefix_bound, (border & id_mask) <= unsigned(n) ? int(border & id_mask) : 0);
            for(int i = 1; i < size; i++) {
                int p = links[i] & id_mask, x = text[position(i) - tagged_length(links[i]) - 1] - 'a';
                tree.data[p].mask |= 1U << x;
                links[i] = (x << 24) | p;
            }
            // Beyond the longest repeated prefix, ordinary states are leaves.
            // Their offset entries are never read, so skip that whole interval.
            for(int i = 0; i <= last_branch; i++)
                tree.data[i + 1].offset = tree.data[i].offset + std::popcount(tree.data[i].mask);
            tree.data[n + 1].offset = tree.data[last_branch + 1].offset;
            for(int i = n + 1; i < size; i++)
                tree.data[i + 1].offset = tree.data[i].offset + std::popcount(tree.data[i].mask);
            auto scatter = [&](int i, uint32_t entry) {
                int p = links[i] & id_mask, x = unsigned(links[i]) >> 24;
                int rank = std::popcount(tree.data[p].mask & ((1U << x) - 1));
                children.data[tree.data[p].offset + rank] = entry;
            };
            // Leaves carry answers; clones carry ranges; internal prefixes also emit themselves.
            for(int i = 1; i <= last_branch; i++) scatter(i, uint32_t(i) | dense_tag);
            for(int i = last_branch + 1; i <= n; i++) scatter(i, n - i);
            for(int i = n + 1; i < size; i++)
                scatter(i, (uint32_t(std::popcount(tree.data[i].mask)) << 24) | tree.data[i].offset);
            checkpoint("tree");
            int top = 0, count = 0, cursor = tree.data[0].offset, end = tree.data[1].offset;
            while(true) {
                if(cursor == end) {
                    if(!top) break;
                    end = tree.data[--top].mask;
                    cursor = tree.data[--top].mask;
                    continue;
                }
                if(end - cursor >= 2) {
                    uint64_t pair;
                    std::memcpy(&pair, children.data + cursor, sizeof(pair));
                    if(!(pair & 0xFF000000FF000000ULL)) {
                        std::memcpy(links + count, &pair, sizeof(pair));
                        count += 2; cursor += 2;
                        continue;
                    }
                }
                uint32_t entry = children.data[cursor++];
                if(!(entry >> 24)) { links[count++] = entry; continue; }
                int begin, finish;
                if(entry & dense_tag) {
                    int u = entry & id_mask;
                    links[count++] = n - u;
                    begin = tree.data[u].offset;
                    finish = tree.data[u + 1].offset;
                } else {
                    begin = entry & id_mask;
                    finish = begin + (entry >> 24);
                }
                if(cursor != end) {
                    tree.data[top++].mask = cursor;
                    tree.data[top++].mask = end;
                }
                cursor = begin;
                end = finish;
            }
            checkpoint("dfs");
            link.resize(n);
            return std::move(link);
        }
    };

    inline auto suffix_array(std::string text) {
        std::ranges::reverse(text);
        return suffix_automaton(std::move(text), true).take_suffix_order();
    }
}
#endif // CP_ALGO_STRUCTURES_SUFFIX_AUTOMATON_HPP

#line 1 "cp-algo/structures/suffix_automaton.hpp"


#include <algorithm>
#include <array>
#include <bit>
#include <cassert>
#include <cstdint>
#include <cstdlib>
#include <cstring>
#include <limits>
#include <memory>
#include <new>
#include <string>
#include <string_view>
#include <utility>
#include <vector>
#line 1 "cp-algo/util/big_alloc.hpp"



#include <set>
#include <map>
#include <deque>
#include <stack>
#include <queue>
#line 11 "cp-algo/util/big_alloc.hpp"
#include <cstddef>
#include <iostream>
#include <forward_list>

// Single macro to detect POSIX platforms (Linux, Unix, macOS)
#if defined(__linux__) || defined(__unix__) || (defined(__APPLE__) && defined(__MACH__))
#  define CP_ALGO_USE_MMAP 1
#  include <sys/mman.h>
#else
#  define CP_ALGO_USE_MMAP 0
#endif

namespace cp_algo {
    template <typename T, size_t Align = 32>
    class big_alloc {
        static_assert( Align >= alignof(void*), "Align must be at least pointer-size");
        static_assert(std::popcount(Align) == 1, "Align must be a power of two");
    public:
        using value_type = T;
        template <class U> struct rebind { using other = big_alloc<U, Align>; };
        constexpr bool operator==(const big_alloc&) const = default;
        constexpr bool operator!=(const big_alloc&) const = default;

        big_alloc() noexcept = default;
        template <typename U, std::size_t A>
        big_alloc(const big_alloc<U, A>&) noexcept {}

        [[nodiscard]] T* allocate(std::size_t n) {
            std::size_t padded = round_up(n * sizeof(T));
            std::size_t align = std::max<std::size_t>(alignof(T),  Align);
#if CP_ALGO_USE_MMAP
            if (padded >= MEGABYTE) {
                void* raw = mmap(nullptr, padded,
                                PROT_READ | PROT_WRITE,
                                MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
                madvise(raw, padded, MADV_HUGEPAGE);
                return static_cast<T*>(raw);
            }
#endif
            return static_cast<T*>(::operator new(padded, std::align_val_t(align)));
        }

        void deallocate(T* p, std::size_t n) noexcept {
            if (!p) return;
            std::size_t padded = round_up(n * sizeof(T));
            std::size_t align  = std::max<std::size_t>(alignof(T),  Align);
    #if CP_ALGO_USE_MMAP
            if (padded >= MEGABYTE) { munmap(p, padded); return; }
    #endif
            ::operator delete(p, padded, std::align_val_t(align));
        }

    private:
        static constexpr std::size_t MEGABYTE = 1 << 20;
        static constexpr std::size_t round_up(std::size_t x) noexcept {
            return (x + Align - 1) / Align * Align;
        }
    };

    template<typename T> using big_vector = std::vector<T, big_alloc<T>>;
    template<typename T> using big_basic_string = std::basic_string<T, std::char_traits<T>, big_alloc<T>>;
    template<typename T> using big_deque = std::deque<T, big_alloc<T>>;
    template<typename T> using big_stack = std::stack<T, big_deque<T>>;
    template<typename T> using big_queue = std::queue<T, big_deque<T>>;
    template<typename T> using big_priority_queue = std::priority_queue<T, big_vector<T>>;
    template<typename T> using big_forward_list = std::forward_list<T, big_alloc<T>>;
    using big_string = big_basic_string<char>;

    template<typename Key, typename Value, typename Compare = std::less<Key>>
    using big_map = std::map<Key, Value, Compare, big_alloc<std::pair<const Key, Value>>>;
    template<typename T, typename Compare = std::less<T>>
    using big_multiset = std::multiset<T, Compare, big_alloc<T>>;
    template<typename T, typename Compare = std::less<T>>
    using big_set = std::set<T, Compare, big_alloc<T>>;
}


#line 1 "cp-algo/util/checkpoint.hpp"


#line 5 "cp-algo/util/checkpoint.hpp"
#include <chrono>
#line 8 "cp-algo/util/checkpoint.hpp"
namespace cp_algo {
#ifdef CP_ALGO_CHECKPOINT
    big_map<big_string, double> checkpoints;
    double last;
#endif
    template<bool final = false>
    void checkpoint([[maybe_unused]] auto const& _msg) {
#ifdef CP_ALGO_CHECKPOINT
        big_string msg = _msg;
        double now = (double)clock() / CLOCKS_PER_SEC;
        double delta = now - last;
        last = now;
        if(msg.size() && !final) {
            checkpoints[msg] += delta;
        }
        if(final) {
            for(auto const& [key, value] : checkpoints) {
                std::cerr << key << ": " << value * 1000 << " ms\n";
            }
            std::cerr << "Total: " << now * 1000 << " ms\n";
        }
#endif
    }
    template<bool final = false>
    void checkpoint() {
        checkpoint<final>("");
    }
}

#line 19 "cp-algo/structures/suffix_automaton.hpp"

namespace cp_algo::structures {
    auto suffix_array(std::string text);

    // An immutable substring index for lowercase Latin letters.
    // Packed state IDs support strings of fewer than 2^23 characters.
    class suffix_automaton {
    public:
        explicit suffix_automaton(std::string text): suffix_automaton(std::move(text), false) {}

        int64_t count_distinct() const { return distinct; }

        // Half-open intervals [a,b) in the indexed text and [c,d) in other.
        std::array<int, 4> longest_common_substring(std::string_view other) const {
            switch(width) {
                case 0: return match<0>(other);
                case 1: return match<1>(other);
                case 2: return match<2>(other);
                case 4: return match<4>(other);
                default: return match<-1>(other);
            }
        }

    private:
        friend auto suffix_array(std::string text);
        // Align large mappings to huge-page boundaries. This policy is local to SAM.
        template<class T> struct page_allocator {
            using value_type = T;
            template<class U> struct rebind { using other = page_allocator<U>; };
            page_allocator() = default;
            template<class U> page_allocator(page_allocator<U> const&) {}
            bool operator==(page_allocator const&) const { return true; }
            static constexpr size_t page = 1U << 21, threshold = 1U << 20;
            T* allocate(size_t count) {
                if(count > (std::numeric_limits<size_t>::max() - 2 * page) / sizeof(T))
                    throw std::bad_array_new_length();
                size_t bytes = count * sizeof(T);
#ifdef __linux__
                if(bytes >= threshold) {
                    bytes = (bytes + page - 1) & -page;
                    void *raw = mmap(nullptr, bytes + page, PROT_READ | PROT_WRITE,
                                     MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
                    if(raw == MAP_FAILED) throw std::bad_alloc();
                    uintptr_t begin = (uintptr_t(raw) + page - 1) & -page;
                    size_t before = begin - uintptr_t(raw), after = page - before;
                    if(before) munmap(raw, before);
                    if(after) munmap(reinterpret_cast<void*>(begin + bytes), after);
                    madvise(reinterpret_cast<void*>(begin), bytes, MADV_HUGEPAGE);
                    return reinterpret_cast<T*>(begin);
                }
#endif
                auto p = static_cast<T*>(std::calloc(std::max(count, size_t(1)), sizeof(T)));
                if(!p) throw std::bad_alloc();
                return p;
            }
            void deallocate(T *p, size_t count) {
#ifdef __linux__
                if(count * sizeof(T) >= threshold) {
                    munmap(p, (count * sizeof(T) + page - 1) & -page);
                    return;
                }
#endif
                std::free(p);
            }
        };
        template<class T> using storage = std::vector<T, page_allocator<T>>;
        using row = std::array<int, 26>;
        // Newly mapped pages are zero. Begin row lifetimes without touching every page.
        template<class T> struct zero_storage {
            T *data = nullptr;
            size_t capacity = 0;
            zero_storage() = default;
            explicit zero_storage(size_t n): data(page_allocator<T>{}.allocate(n)), capacity(n) {
                std::uninitialized_default_construct_n(data, n);
            }
            zero_storage(zero_storage const &other): zero_storage(other.capacity) {
                if(capacity) std::copy_n(other.data, capacity, data);
            }
            zero_storage(zero_storage &&other) noexcept { swap(other); }
            zero_storage &operator=(zero_storage other) noexcept { swap(other); return *this; }
            void swap(zero_storage &other) noexcept {
                std::swap(data, other.data); std::swap(capacity, other.capacity);
            }
            ~zero_storage() { if(data) page_allocator<T>{}.deallocate(data, capacity); }
        };
        struct clone_data { int len, pos; };
        struct transitions { uint32_t a = 0, b = 0; };
        static constexpr uint32_t dense_tag = 0x80000000, id_mask = 0xFFFFFF;
        std::string word;
        int n = 0, alphabet = 26, width = 0;
        int64_t distinct = 0;
        std::array<int, 26> code{};
        storage<clone_data> clones;
        storage<int> link, flat;
        storage<transitions> to;
        storage<row> dense;
        zero_storage<row> clone_edges, prefix_edges;
        int prefix_bound = 0;

        suffix_automaton(std::string text, bool suffix_order): word(std::move(text)) {
            assert(word.size() < (1U << 23));
            n = (int)word.size();
            if(suffix_order) {
                for(int c = 0; c < 26; c++) code[c] = c;
            } else {
                code.fill(-1);
                uint32_t letters = 0;
                for(unsigned char c: word) {
                    assert(c >= 'a' && c <= 'z');
                    letters |= 1U << (c - 'a');
                }
                alphabet = 0;
                for(int c = 0; c < 26; c++) {
                    if(letters >> c & 1) code[c] = alphabet++;
                }
                if(alphabet != 26) {
                    for(char &c: word) c = char('a' + code[c - 'a']);
                }
                if(alphabet <= 1) width = 1;
                else if(alphabet <= 2) width = 2;
                else if(alphabet <= 4) width = 4;
                // Avoid tagged lookups while the ordinary dense rows fit in 32 MiB.
                else if(alphabet <= 16 || size_t(n) * alphabet <= (1U << 23)) width = -1;
            }
            clones.reserve(n);
            link.resize(2 * n + 1);
            if(suffix_order) {
                prefix_edges = zero_storage<row>(n + 1);
                clone_edges = zero_storage<row>(n);
            } else if(width == 0) {
                // At most one dense row per state, including clones.
                dense.reserve(link.size());
                to.reserve(link.size());
                to.resize(n + 1);
            } else {
                flat.resize(link.size() * (width > 0 ? width : alphabet));
            }
            checkpoint("init");
            if(suffix_order) {
                build<0, false, true>();
            }
            else switch(width) {
                case 0: build<0>(); break;
                case 1: build<1>(); break;
                case 2: build<2>(); break;
                case 4: build<4>(); break;
                default: build<-1>();
            }
            checkpoint("build");
        }

        int states() const { return n + 1 + (int)clones.size(); }
        // Ordinary state i represents prefix i; only clones need stored metadata.
        int length(int v) const { return v <= n ? v : clones[v - n - 1].len; }
        int position(int v) const { return v <= n ? v : clones[v - n - 1].pos; }

        static row &clone_row(int p, uintptr_t base) {
            return *reinterpret_cast<row*>(base + size_t(p) * sizeof(row));
        }
        template<int Width, bool CloneDense = false>
        int get(int p, int x, uintptr_t clone_base = 0) const {
            if constexpr(CloneDense) {
                if(p > n) return clone_row(p, clone_base)[x];
                // A prefix state's first edge is always p -> p+1 and never redirected.
                if(word[p] == char('a' + x)) return p + 1;
                return p <= prefix_bound ? prefix_edges.data[p][x] : 0;
            }
            if constexpr(Width != 0) {
                return flat[size_t(p) * (Width > 0 ? Width : alphabet) + x];
            } else {
                auto t = to[p];
                if(t.a & dense_tag) return dense[t.a & ~dense_tag][x];
                if((t.a >> 24) == unsigned(x + 1)) return int(t.a & id_mask);
                if((t.b >> 24) == unsigned(x + 1)) return int(t.b & id_mask);
                return 0;
            }
        }
        template<int Width, bool CloneDense = false>
        void set(int p, int x, int v, uintptr_t clone_base = 0) {
            if constexpr(CloneDense) {
                if(p > n) { clone_row(p, clone_base)[x] = v; return; }
                prefix_bound = std::max(prefix_bound, p);
                prefix_edges.data[p][x] = v;
                return;
            }
            if constexpr(Width != 0) {
                flat[size_t(p) * (Width > 0 ? Width : alphabet) + x] = v;
            } else {
                auto &t = to[p];
                auto encoded = (uint32_t(x + 1) << 24) | v;
                if(t.a & dense_tag) dense[t.a & ~dense_tag][x] = v;
                else if(!t.a || (t.a >> 24) == unsigned(x + 1)) t.a = encoded;
                else if(!t.b || (t.b >> 24) == unsigned(x + 1)) t.b = encoded;
                else {
                    std::array<int, 26> row{};
                    row[(t.a >> 24) - 1] = t.a & id_mask;
                    row[(t.b >> 24) - 1] = t.b & id_mask;
                    row[x] = v;
                    t.a = dense_tag | uint32_t(dense.size());
                    dense.push_back(row);
                }
            }
        }
        // In suffix-order mode the high byte caches immutable clone lengths.
        // Zero denotes an ordinary state; 255 falls back to full metadata.
        int tagged_length(uint32_t v) const {
            int len = v >> 24;
            return len == 255 ? length(v & id_mask) : len ? len : int(v & id_mask);
        }
        template<int Width, bool Count = true, bool CloneDense = false>
        void build() {
            auto state_id = [](uint32_t v) -> int {
                if constexpr(CloneDense) return v & id_mask;
                else return v;
            };
            auto state_length = [&](uint32_t v) {
                if constexpr(CloneDense) return tagged_length(v);
                else return length(v);
            };
            // Compute the ID-to-row adjustment once, outside the lookup dependency chain.
            uintptr_t clone_base = 0;
            if constexpr(CloneDense)
                clone_base = reinterpret_cast<uintptr_t>(clone_edges.data) - size_t(n + 1) * sizeof(row);
            int last = 0;
            for(unsigned char c: word) {
                int x = c - 'a';
                uint32_t current = last;
                if constexpr(CloneDense) {
                    // The first edge of the newest prefix is implicit.
                    current = link[last];
                }
                int p = state_id(current);
                ++last;
                uint32_t found;
                while(!(found = get<Width, CloneDense>(p, x, clone_base))) {
                    set<Width, CloneDense>(p, x, last, clone_base);
                    current = link[p];
                    p = state_id(current);
                }
                int q = state_id(found);
                if(q != last) {
                    int len = state_length(current) + 1;
                    if(state_length(found) == len) link[last] = found;
                    else {
                        int clone = states();
                        clones.push_back({len, position(q)});
                        if constexpr(CloneDense) {
                            auto &copy = clone_row(clone, clone_base);
                            if(q > n) copy = clone_row(q, clone_base);
                            else {
                                if(q <= prefix_bound) copy = prefix_edges.data[q];
                                copy[word[q] - 'a'] = q + 1;
                            }
                        } else if constexpr(Width != 0) {
                            int stride = Width > 0 ? Width : alphabet;
                            std::copy_n(flat.data() + size_t(q) * stride, stride,
                                        flat.data() + size_t(clone) * stride);
                        } else {
                            auto row = to[q];
                            if(row.a & dense_tag) {
                                auto copy = dense[row.a & ~dense_tag];
                                row.a = dense_tag | uint32_t(dense.size());
                                dense.push_back(copy);
                            }
                            to.push_back(row);
                        }
                        uint32_t tagged = clone;
                        if constexpr(CloneDense) tagged |= uint32_t(std::min(len, 255)) << 24;
                        link[last] = link[q] = tagged;
                        uint32_t next;
                        while(state_id(next = get<Width, CloneDense>(p, x, clone_base)) == q) {
                            set<Width, CloneDense>(p, x, tagged, clone_base);
                            current = link[p];
                            p = state_id(current);
                        }
                        // The first different end-position class is the clone's suffix link.
                        // Redirecting at the root makes that final transition the clone itself.
                        link[clone] = state_id(next) == clone ? 0 : next;
                    }
                }
                if constexpr(Count) distinct += last - length(link[last]);
            }
        }
        template<int Width>
        std::array<int, 4> match(std::string_view other) const {
            int v = 0, matched = 0, best = 0, end_s = 0, end_t = 0;
            for(int i = 0; i < (int)other.size(); i++) {
                unsigned c = (unsigned char)other[i] - unsigned('a');
                int x = c < 26 ? code[c] : -1;
                if(x < 0) { v = matched = 0; continue; }
                while(v && !get<Width>(v, x)) {
                    v = link[v];
                    matched = length(v);
                }
                v = get<Width>(v, x);
                matched = v ? matched + 1 : 0;
                if(matched > best) { best = matched; end_s = position(v); end_t = i + 1; }
            }
            checkpoint("query");
            return {end_s - best, end_s, end_t - best, end_t};
        }

        // Consumes a temporary SAM of the reversed input. No storage mutation is public.
        [[gnu::always_inline]] auto take_suffix_order() && {
            dense = decltype(dense){};
            clone_edges = zero_storage<row>{};
            prefix_edges = zero_storage<row>{};
            int size = states();
            const int n = this->n;
            auto links = link.data();
            auto text = word.data();
            auto clone = clones.data();
            auto position = [&](int v) { return v <= n ? v : clone[v - n - 1].pos; };
            auto tagged_length = [&](uint32_t v) {
                int len = v >> 24;
                return len == 255 ? (int(v & id_mask) <= n ? int(v & id_mask) : clone[(v & id_mask) - n - 1].len)
                                  : len ? len : int(v & id_mask);
            };
            struct tree_node { uint32_t offset, mask; };
            zero_storage<tree_node> tree(size + 1);
            zero_storage<int> children(size);
            uint32_t border = links[n];
            while((border & id_mask) > unsigned(n) && tagged_length(border) > prefix_bound)
                border = links[border & id_mask];
            int last_branch = std::max(prefix_bound, (border & id_mask) <= unsigned(n) ? int(border & id_mask) : 0);
            for(int i = 1; i < size; i++) {
                int p = links[i] & id_mask, x = text[position(i) - tagged_length(links[i]) - 1] - 'a';
                tree.data[p].mask |= 1U << x;
                links[i] = (x << 24) | p;
            }
            // Beyond the longest repeated prefix, ordinary states are leaves.
            // Their offset entries are never read, so skip that whole interval.
            for(int i = 0; i <= last_branch; i++)
                tree.data[i + 1].offset = tree.data[i].offset + std::popcount(tree.data[i].mask);
            tree.data[n + 1].offset = tree.data[last_branch + 1].offset;
            for(int i = n + 1; i < size; i++)
                tree.data[i + 1].offset = tree.data[i].offset + std::popcount(tree.data[i].mask);
            auto scatter = [&](int i, uint32_t entry) {
                int p = links[i] & id_mask, x = unsigned(links[i]) >> 24;
                int rank = std::popcount(tree.data[p].mask & ((1U << x) - 1));
                children.data[tree.data[p].offset + rank] = entry;
            };
            // Leaves carry answers; clones carry ranges; internal prefixes also emit themselves.
            for(int i = 1; i <= last_branch; i++) scatter(i, uint32_t(i) | dense_tag);
            for(int i = last_branch + 1; i <= n; i++) scatter(i, n - i);
            for(int i = n + 1; i < size; i++)
                scatter(i, (uint32_t(std::popcount(tree.data[i].mask)) << 24) | tree.data[i].offset);
            checkpoint("tree");
            int top = 0, count = 0, cursor = tree.data[0].offset, end = tree.data[1].offset;
            while(true) {
                if(cursor == end) {
                    if(!top) break;
                    end = tree.data[--top].mask;
                    cursor = tree.data[--top].mask;
                    continue;
                }
                if(end - cursor >= 2) {
                    uint64_t pair;
                    std::memcpy(&pair, children.data + cursor, sizeof(pair));
                    if(!(pair & 0xFF000000FF000000ULL)) {
                        std::memcpy(links + count, &pair, sizeof(pair));
                        count += 2; cursor += 2;
                        continue;
                    }
                }
                uint32_t entry = children.data[cursor++];
                if(!(entry >> 24)) { links[count++] = entry; continue; }
                int begin, finish;
                if(entry & dense_tag) {
                    int u = entry & id_mask;
                    links[count++] = n - u;
                    begin = tree.data[u].offset;
                    finish = tree.data[u + 1].offset;
                } else {
                    begin = entry & id_mask;
                    finish = begin + (entry >> 24);
                }
                if(cursor != end) {
                    tree.data[top++].mask = cursor;
                    tree.data[top++].mask = end;
                }
                cursor = begin;
                end = finish;
            }
            checkpoint("dfs");
            link.resize(n);
            return std::move(link);
        }
    };

    inline auto suffix_array(std::string text) {
        std::ranges::reverse(text);
        return suffix_automaton(std::move(text), true).take_suffix_order();
    }
}


#ifndef CP_ALGO_STRUCTURES_SUFFIX_AUTOMATON_HPP
#define CP_ALGO_STRUCTURES_SUFFIX_AUTOMATON_HPP
#include <algorithm>
#include <array>
#include <bit>
#include <cassert>
#include <cstdint>
#include <cstdlib>
#include <cstring>
#include <limits>
#include <memory>
#include <new>
#include <string>
#include <string_view>
#include <utility>
#include <vector>
#include "../util/big_alloc.hpp"
#include "../util/checkpoint.hpp"
namespace cp_algo::structures{auto suffix_array(std::string text);class suffix_automaton{public:explicit suffix_automaton(std::string text):suffix_automaton(std::move(text),false){}int64_t count_distinct()const{return distinct;}std::array<int,4>longest_common_substring(std::string_view other)const{switch(width){case 0:return match<0>(other);case 1:return match<1>(other);case 2:return match<2>(other);case 4:return match<4>(other);default:return match<-1>(other);}}private:friend auto suffix_array(std::string text);template<class T>struct page_allocator{using value_type=T;template<class U>struct rebind{using other=page_allocator<U>;};page_allocator()=default;template<class U>page_allocator(page_allocator<U>const&){}bool operator==(page_allocator const&)const{return true;}static constexpr size_t page=1U<<21,threshold=1U<<20;T*allocate(size_t count){if(count>(std::numeric_limits<size_t>::max()-2*page)/sizeof(T))throw std::bad_array_new_length();size_t bytes=count*sizeof(T);
#ifdef __linux__
if(bytes>=threshold){bytes=(bytes+page-1)&-page;void*raw=mmap(nullptr,bytes+page,PROT_READ|PROT_WRITE,MAP_PRIVATE|MAP_ANONYMOUS,-1,0);if(raw==MAP_FAILED)throw std::bad_alloc();uintptr_t begin=(uintptr_t(raw)+page-1)&-page;size_t before=begin-uintptr_t(raw),after=page-before;if(before)munmap(raw,before);if(after)munmap(reinterpret_cast<void*>(begin+bytes),after);madvise(reinterpret_cast<void*>(begin),bytes,MADV_HUGEPAGE);return reinterpret_cast<T*>(begin);}
#endif
auto p=static_cast<T*>(std::calloc(std::max(count,size_t(1)),sizeof(T)));if(!p)throw std::bad_alloc();return p;}void deallocate(T*p,size_t count){
#ifdef __linux__
if(count*sizeof(T)>=threshold){munmap(p,(count*sizeof(T)+page-1)&-page);return;}
#endif
std::free(p);}};template<class T>using storage=std::vector<T,page_allocator<T>>;using row=std::array<int,26>;template<class T>struct zero_storage{T*data=nullptr;size_t capacity=0;zero_storage()=default;explicit zero_storage(size_t n):data(page_allocator<T>{}.allocate(n)),capacity(n){std::uninitialized_default_construct_n(data,n);}zero_storage(zero_storage const&other):zero_storage(other.capacity){if(capacity)std::copy_n(other.data,capacity,data);}zero_storage(zero_storage&&other)noexcept{swap(other);}zero_storage&operator=(zero_storage other)noexcept{swap(other);return*this;}void swap(zero_storage&other)noexcept{std::swap(data,other.data);std::swap(capacity,other.capacity);}~zero_storage(){if(data)page_allocator<T>{}.deallocate(data,capacity);}};struct clone_data{int len,pos;};struct transitions{uint32_t a=0,b=0;};static constexpr uint32_t dense_tag=0x80000000,id_mask=0xFFFFFF;std::string word;int n=0,alphabet=26,width=0;int64_t distinct=0;std::array<int,26>code{};storage<clone_data>clones;storage<int>link,flat;storage<transitions>to;storage<row>dense;zero_storage<row>clone_edges,prefix_edges;int prefix_bound=0;suffix_automaton(std::string text,bool suffix_order):word(std::move(text)){assert(word.size()<(1U<<23));n=(int)word.size();if(suffix_order){for(int c=0;c<26;c++)code[c]=c;}else{code.fill(-1);uint32_t letters=0;for(unsigned char c:word){assert(c>='a'&&c<='z');letters|=1U<<(c-'a');}alphabet=0;for(int c=0;c<26;c++){if(letters>>c&1)code[c]=alphabet++;}if(alphabet!=26){for(char&c:word)c=char('a'+code[c-'a']);}if(alphabet<=1)width=1;else if(alphabet<=2)width=2;else if(alphabet<=4)width=4;else if(alphabet<=16||size_t(n)*alphabet<=(1U<<23))width=-1;}clones.reserve(n);link.resize(2*n+1);if(suffix_order){prefix_edges=zero_storage<row>(n+1);clone_edges=zero_storage<row>(n);}else if(width==0){dense.reserve(link.size());to.reserve(link.size());to.resize(n+1);}else{flat.resize(link.size()*(width>0?width:alphabet));}checkpoint("init");if(suffix_order){build<0,false,true>();}else switch(width){case 0:build<0>();break;case 1:build<1>();break;case 2:build<2>();break;case 4:build<4>();break;default:build<-1>();}checkpoint("build");}int states()const{return n+1+(int)clones.size();}int length(int v)const{return v<=n?v:clones[v-n-1].len;}int position(int v)const{return v<=n?v:clones[v-n-1].pos;}static row&clone_row(int p,uintptr_t base){return*reinterpret_cast<row*>(base+size_t(p)*sizeof(row));}template<int Width,bool CloneDense=false>int get(int p,int x,uintptr_t clone_base=0)const{if constexpr(CloneDense){if(p>n)return clone_row(p,clone_base)[x];if(word[p]==char('a'+x))return p+1;return p<=prefix_bound?prefix_edges.data[p][x]:0;}if constexpr(Width!=0){return flat[size_t(p)*(Width>0?Width:alphabet)+x];}else{auto t=to[p];if(t.a&dense_tag)return dense[t.a&~dense_tag][x];if((t.a>>24)==unsigned(x+1))return int(t.a&id_mask);if((t.b>>24)==unsigned(x+1))return int(t.b&id_mask);return 0;}}template<int Width,bool CloneDense=false>void set(int p,int x,int v,uintptr_t clone_base=0){if constexpr(CloneDense){if(p>n){clone_row(p,clone_base)[x]=v;return;}prefix_bound=std::max(prefix_bound,p);prefix_edges.data[p][x]=v;return;}if constexpr(Width!=0){flat[size_t(p)*(Width>0?Width:alphabet)+x]=v;}else{auto&t=to[p];auto encoded=(uint32_t(x+1)<<24)|v;if(t.a&dense_tag)dense[t.a&~dense_tag][x]=v;else if(!t.a||(t.a>>24)==unsigned(x+1))t.a=encoded;else if(!t.b||(t.b>>24)==unsigned(x+1))t.b=encoded;else{std::array<int,26>row{};row[(t.a>>24)-1]=t.a&id_mask;row[(t.b>>24)-1]=t.b&id_mask;row[x]=v;t.a=dense_tag|uint32_t(dense.size());dense.push_back(row);}}}int tagged_length(uint32_t v)const{int len=v>>24;return len==255?length(v&id_mask):len?len:int(v&id_mask);}template<int Width,bool Count=true,bool CloneDense=false>void build(){auto state_id=[](uint32_t v)->int{if constexpr(CloneDense)return v&id_mask;else return v;};auto state_length=[&](uint32_t v){if constexpr(CloneDense)return tagged_length(v);else return length(v);};uintptr_t clone_base=0;if constexpr(CloneDense)clone_base=reinterpret_cast<uintptr_t>(clone_edges.data)-size_t(n+1)*sizeof(row);int last=0;for(unsigned char c:word){int x=c-'a';uint32_t current=last;if constexpr(CloneDense){current=link[last];}int p=state_id(current);++last;uint32_t found;while(!(found=get<Width,CloneDense>(p,x,clone_base))){set<Width,CloneDense>(p,x,last,clone_base);current=link[p];p=state_id(current);}int q=state_id(found);if(q!=last){int len=state_length(current)+1;if(state_length(found)==len)link[last]=found;else{int clone=states();clones.push_back({len,position(q)});if constexpr(CloneDense){auto&copy=clone_row(clone,clone_base);if(q>n)copy=clone_row(q,clone_base);else{if(q<=prefix_bound)copy=prefix_edges.data[q];copy[word[q]-'a']=q+1;}}else if constexpr(Width!=0){int stride=Width>0?Width:alphabet;std::copy_n(flat.data()+size_t(q)*stride,stride,flat.data()+size_t(clone)*stride);}else{auto row=to[q];if(row.a&dense_tag){auto copy=dense[row.a&~dense_tag];row.a=dense_tag|uint32_t(dense.size());dense.push_back(copy);}to.push_back(row);}uint32_t tagged=clone;if constexpr(CloneDense)tagged|=uint32_t(std::min(len,255))<<24;link[last]=link[q]=tagged;uint32_t next;while(state_id(next=get<Width,CloneDense>(p,x,clone_base))==q){set<Width,CloneDense>(p,x,tagged,clone_base);current=link[p];p=state_id(current);}link[clone]=state_id(next)==clone?0:next;}}if constexpr(Count)distinct+=last-length(link[last]);}}template<int Width>std::array<int,4>match(std::string_view other)const{int v=0,matched=0,best=0,end_s=0,end_t=0;for(int i=0;i<(int)other.size();i++){unsigned c=(unsigned char)other[i]-unsigned('a');int x=c<26?code[c]:-1;if(x<0){v=matched=0;continue;}while(v&&!get<Width>(v,x)){v=link[v];matched=length(v);}v=get<Width>(v,x);matched=v?matched+1:0;if(matched>best){best=matched;end_s=position(v);end_t=i+1;}}checkpoint("query");return{end_s-best,end_s,end_t-best,end_t};}[[gnu::always_inline]]auto take_suffix_order()&&{dense=decltype(dense){};clone_edges=zero_storage<row>{};prefix_edges=zero_storage<row>{};int size=states();const int n=this->n;auto links=link.data();auto text=word.data();auto clone=clones.data();auto position=[&](int v){return v<=n?v:clone[v-n-1].pos;};auto tagged_length=[&](uint32_t v){int len=v>>24;return len==255?(int(v&id_mask)<=n?int(v&id_mask):clone[(v&id_mask)-n-1].len):len?len:int(v&id_mask);};struct tree_node{uint32_t offset,mask;};zero_storage<tree_node>tree(size+1);zero_storage<int>children(size);uint32_t border=links[n];while((border&id_mask)>unsigned(n)&&tagged_length(border)>prefix_bound)border=links[border&id_mask];int last_branch=std::max(prefix_bound,(border&id_mask)<=unsigned(n)?int(border&id_mask):0);for(int i=1;i<size;i++){int p=links[i]&id_mask,x=text[position(i)-tagged_length(links[i])-1]-'a';tree.data[p].mask|=1U<<x;links[i]=(x<<24)|p;}for(int i=0;i<=last_branch;i++)tree.data[i+1].offset=tree.data[i].offset+std::popcount(tree.data[i].mask);tree.data[n+1].offset=tree.data[last_branch+1].offset;for(int i=n+1;i<size;i++)tree.data[i+1].offset=tree.data[i].offset+std::popcount(tree.data[i].mask);auto scatter=[&](int i,uint32_t entry){int p=links[i]&id_mask,x=unsigned(links[i])>>24;int rank=std::popcount(tree.data[p].mask&((1U<<x)-1));children.data[tree.data[p].offset+rank]=entry;};for(int i=1;i<=last_branch;i++)scatter(i,uint32_t(i)|dense_tag);for(int i=last_branch+1;i<=n;i++)scatter(i,n-i);for(int i=n+1;i<size;i++)scatter(i,(uint32_t(std::popcount(tree.data[i].mask))<<24)|tree.data[i].offset);checkpoint("tree");int top=0,count=0,cursor=tree.data[0].offset,end=tree.data[1].offset;while(true){if(cursor==end){if(!top)break;end=tree.data[--top].mask;cursor=tree.data[--top].mask;continue;}if(end-cursor>=2){uint64_t pair;std::memcpy(&pair,children.data+cursor,sizeof(pair));if(!(pair&0xFF000000FF000000ULL)){std::memcpy(links+count,&pair,sizeof(pair));count+=2;cursor+=2;continue;}}uint32_t entry=children.data[cursor++];if(!(entry>>24)){links[count++]=entry;continue;}int begin,finish;if(entry&dense_tag){int u=entry&id_mask;links[count++]=n-u;begin=tree.data[u].offset;finish=tree.data[u+1].offset;}else{begin=entry&id_mask;finish=begin+(entry>>24);}if(cursor!=end){tree.data[top++].mask=cursor;tree.data[top++].mask=end;}cursor=begin;end=finish;}checkpoint("dfs");link.resize(n);return std::move(link);}};inline auto suffix_array(std::string text){std::ranges::reverse(text);return suffix_automaton(std::move(text),true).take_suffix_order();}}
#endif

#line 1 "cp-algo/structures/suffix_automaton.hpp"
#include <algorithm>
#include <array>
#include <bit>
#include <cassert>
#include <cstdint>
#include <cstdlib>
#include <cstring>
#include <limits>
#include <memory>
#include <new>
#include <string>
#include <string_view>
#include <utility>
#include <vector>
#line 1 "cp-algo/util/big_alloc.hpp"
#include <set>
#include <map>
#include <deque>
#include <stack>
#include <queue>
#line 11 "cp-algo/util/big_alloc.hpp"
#include <cstddef>
#include <iostream>
#include <forward_list>
#if defined(__linux__) || defined(__unix__) || (defined(__APPLE__) && defined(__MACH__))
#  define CP_ALGO_USE_MMAP 1
#  include <sys/mman.h>
#else
#  define CP_ALGO_USE_MMAP 0
#endif
namespace cp_algo{template<typename T,size_t Align=32>class big_alloc{static_assert(Align>=alignof(void*),"Align must be at least pointer-size");static_assert(std::popcount(Align)==1,"Align must be a power of two");public:using value_type=T;template<class U>struct rebind{using other=big_alloc<U,Align>;};constexpr bool operator==(const big_alloc&)const=default;constexpr bool operator!=(const big_alloc&)const=default;big_alloc()noexcept=default;template<typename U,std::size_t A>big_alloc(const big_alloc<U,A>&)noexcept{}[[nodiscard]]T*allocate(std::size_t n){std::size_t padded=round_up(n*sizeof(T));std::size_t align=std::max<std::size_t>(alignof(T),Align);
#if CP_ALGO_USE_MMAP
if(padded>=MEGABYTE){void*raw=mmap(nullptr,padded,PROT_READ|PROT_WRITE,MAP_PRIVATE|MAP_ANONYMOUS,-1,0);madvise(raw,padded,MADV_HUGEPAGE);return static_cast<T*>(raw);}
#endif
return static_cast<T*>(::operator new(padded,std::align_val_t(align)));}void deallocate(T*p,std::size_t n)noexcept{if(!p)return;std::size_t padded=round_up(n*sizeof(T));std::size_t align=std::max<std::size_t>(alignof(T),Align);
#if CP_ALGO_USE_MMAP
if(padded>=MEGABYTE){munmap(p,padded);return;}
#endif
::operator delete(p,padded,std::align_val_t(align));}private:static constexpr std::size_t MEGABYTE=1<<20;static constexpr std::size_t round_up(std::size_t x)noexcept{return(x+Align-1)/Align*Align;}};template<typename T>using big_vector=std::vector<T,big_alloc<T>>;template<typename T>using big_basic_string=std::basic_string<T,std::char_traits<T>,big_alloc<T>>;template<typename T>using big_deque=std::deque<T,big_alloc<T>>;template<typename T>using big_stack=std::stack<T,big_deque<T>>;template<typename T>using big_queue=std::queue<T,big_deque<T>>;template<typename T>using big_priority_queue=std::priority_queue<T,big_vector<T>>;template<typename T>using big_forward_list=std::forward_list<T,big_alloc<T>>;using big_string=big_basic_string<char>;template<typename Key,typename Value,typename Compare=std::less<Key>>using big_map=std::map<Key,Value,Compare,big_alloc<std::pair<const Key,Value>>>;template<typename T,typename Compare=std::less<T>>using big_multiset=std::multiset<T,Compare,big_alloc<T>>;template<typename T,typename Compare=std::less<T>>using big_set=std::set<T,Compare,big_alloc<T>>;}
#line 1 "cp-algo/util/checkpoint.hpp"
#line 5 "cp-algo/util/checkpoint.hpp"
#include <chrono>
#line 8 "cp-algo/util/checkpoint.hpp"
namespace cp_algo{
#ifdef CP_ALGO_CHECKPOINT
big_map<big_string,double>checkpoints;double last;
#endif
template<bool final=false>void checkpoint([[maybe_unused]]auto const&_msg){
#ifdef CP_ALGO_CHECKPOINT
big_string msg=_msg;double now=(double)clock()/CLOCKS_PER_SEC;double delta=now-last;last=now;if(msg.size()&&!final){checkpoints[msg]+=delta;}if(final){for(auto const&[key,value]:checkpoints){std::cerr<<key<<": "<<value*1000<<" ms\n";}std::cerr<<"Total: "<<now*1000<<" ms\n";}
#endif
}template<bool final=false>void checkpoint(){checkpoint<final>("");}}
#line 19 "cp-algo/structures/suffix_automaton.hpp"
namespace cp_algo::structures{auto suffix_array(std::string text);class suffix_automaton{public:explicit suffix_automaton(std::string text):suffix_automaton(std::move(text),false){}int64_t count_distinct()const{return distinct;}std::array<int,4>longest_common_substring(std::string_view other)const{switch(width){case 0:return match<0>(other);case 1:return match<1>(other);case 2:return match<2>(other);case 4:return match<4>(other);default:return match<-1>(other);}}private:friend auto suffix_array(std::string text);template<class T>struct page_allocator{using value_type=T;template<class U>struct rebind{using other=page_allocator<U>;};page_allocator()=default;template<class U>page_allocator(page_allocator<U>const&){}bool operator==(page_allocator const&)const{return true;}static constexpr size_t page=1U<<21,threshold=1U<<20;T*allocate(size_t count){if(count>(std::numeric_limits<size_t>::max()-2*page)/sizeof(T))throw std::bad_array_new_length();size_t bytes=count*sizeof(T);
#ifdef __linux__
if(bytes>=threshold){bytes=(bytes+page-1)&-page;void*raw=mmap(nullptr,bytes+page,PROT_READ|PROT_WRITE,MAP_PRIVATE|MAP_ANONYMOUS,-1,0);if(raw==MAP_FAILED)throw std::bad_alloc();uintptr_t begin=(uintptr_t(raw)+page-1)&-page;size_t before=begin-uintptr_t(raw),after=page-before;if(before)munmap(raw,before);if(after)munmap(reinterpret_cast<void*>(begin+bytes),after);madvise(reinterpret_cast<void*>(begin),bytes,MADV_HUGEPAGE);return reinterpret_cast<T*>(begin);}
#endif
auto p=static_cast<T*>(std::calloc(std::max(count,size_t(1)),sizeof(T)));if(!p)throw std::bad_alloc();return p;}void deallocate(T*p,size_t count){
#ifdef __linux__
if(count*sizeof(T)>=threshold){munmap(p,(count*sizeof(T)+page-1)&-page);return;}
#endif
std::free(p);}};template<class T>using storage=std::vector<T,page_allocator<T>>;using row=std::array<int,26>;template<class T>struct zero_storage{T*data=nullptr;size_t capacity=0;zero_storage()=default;explicit zero_storage(size_t n):data(page_allocator<T>{}.allocate(n)),capacity(n){std::uninitialized_default_construct_n(data,n);}zero_storage(zero_storage const&other):zero_storage(other.capacity){if(capacity)std::copy_n(other.data,capacity,data);}zero_storage(zero_storage&&other)noexcept{swap(other);}zero_storage&operator=(zero_storage other)noexcept{swap(other);return*this;}void swap(zero_storage&other)noexcept{std::swap(data,other.data);std::swap(capacity,other.capacity);}~zero_storage(){if(data)page_allocator<T>{}.deallocate(data,capacity);}};struct clone_data{int len,pos;};struct transitions{uint32_t a=0,b=0;};static constexpr uint32_t dense_tag=0x80000000,id_mask=0xFFFFFF;std::string word;int n=0,alphabet=26,width=0;int64_t distinct=0;std::array<int,26>code{};storage<clone_data>clones;storage<int>link,flat;storage<transitions>to;storage<row>dense;zero_storage<row>clone_edges,prefix_edges;int prefix_bound=0;suffix_automaton(std::string text,bool suffix_order):word(std::move(text)){assert(word.size()<(1U<<23));n=(int)word.size();if(suffix_order){for(int c=0;c<26;c++)code[c]=c;}else{code.fill(-1);uint32_t letters=0;for(unsigned char c:word){assert(c>='a'&&c<='z');letters|=1U<<(c-'a');}alphabet=0;for(int c=0;c<26;c++){if(letters>>c&1)code[c]=alphabet++;}if(alphabet!=26){for(char&c:word)c=char('a'+code[c-'a']);}if(alphabet<=1)width=1;else if(alphabet<=2)width=2;else if(alphabet<=4)width=4;else if(alphabet<=16||size_t(n)*alphabet<=(1U<<23))width=-1;}clones.reserve(n);link.resize(2*n+1);if(suffix_order){prefix_edges=zero_storage<row>(n+1);clone_edges=zero_storage<row>(n);}else if(width==0){dense.reserve(link.size());to.reserve(link.size());to.resize(n+1);}else{flat.resize(link.size()*(width>0?width:alphabet));}checkpoint("init");if(suffix_order){build<0,false,true>();}else switch(width){case 0:build<0>();break;case 1:build<1>();break;case 2:build<2>();break;case 4:build<4>();break;default:build<-1>();}checkpoint("build");}int states()const{return n+1+(int)clones.size();}int length(int v)const{return v<=n?v:clones[v-n-1].len;}int position(int v)const{return v<=n?v:clones[v-n-1].pos;}static row&clone_row(int p,uintptr_t base){return*reinterpret_cast<row*>(base+size_t(p)*sizeof(row));}template<int Width,bool CloneDense=false>int get(int p,int x,uintptr_t clone_base=0)const{if constexpr(CloneDense){if(p>n)return clone_row(p,clone_base)[x];if(word[p]==char('a'+x))return p+1;return p<=prefix_bound?prefix_edges.data[p][x]:0;}if constexpr(Width!=0){return flat[size_t(p)*(Width>0?Width:alphabet)+x];}else{auto t=to[p];if(t.a&dense_tag)return dense[t.a&~dense_tag][x];if((t.a>>24)==unsigned(x+1))return int(t.a&id_mask);if((t.b>>24)==unsigned(x+1))return int(t.b&id_mask);return 0;}}template<int Width,bool CloneDense=false>void set(int p,int x,int v,uintptr_t clone_base=0){if constexpr(CloneDense){if(p>n){clone_row(p,clone_base)[x]=v;return;}prefix_bound=std::max(prefix_bound,p);prefix_edges.data[p][x]=v;return;}if constexpr(Width!=0){flat[size_t(p)*(Width>0?Width:alphabet)+x]=v;}else{auto&t=to[p];auto encoded=(uint32_t(x+1)<<24)|v;if(t.a&dense_tag)dense[t.a&~dense_tag][x]=v;else if(!t.a||(t.a>>24)==unsigned(x+1))t.a=encoded;else if(!t.b||(t.b>>24)==unsigned(x+1))t.b=encoded;else{std::array<int,26>row{};row[(t.a>>24)-1]=t.a&id_mask;row[(t.b>>24)-1]=t.b&id_mask;row[x]=v;t.a=dense_tag|uint32_t(dense.size());dense.push_back(row);}}}int tagged_length(uint32_t v)const{int len=v>>24;return len==255?length(v&id_mask):len?len:int(v&id_mask);}template<int Width,bool Count=true,bool CloneDense=false>void build(){auto state_id=[](uint32_t v)->int{if constexpr(CloneDense)return v&id_mask;else return v;};auto state_length=[&](uint32_t v){if constexpr(CloneDense)return tagged_length(v);else return length(v);};uintptr_t clone_base=0;if constexpr(CloneDense)clone_base=reinterpret_cast<uintptr_t>(clone_edges.data)-size_t(n+1)*sizeof(row);int last=0;for(unsigned char c:word){int x=c-'a';uint32_t current=last;if constexpr(CloneDense){current=link[last];}int p=state_id(current);++last;uint32_t found;while(!(found=get<Width,CloneDense>(p,x,clone_base))){set<Width,CloneDense>(p,x,last,clone_base);current=link[p];p=state_id(current);}int q=state_id(found);if(q!=last){int len=state_length(current)+1;if(state_length(found)==len)link[last]=found;else{int clone=states();clones.push_back({len,position(q)});if constexpr(CloneDense){auto&copy=clone_row(clone,clone_base);if(q>n)copy=clone_row(q,clone_base);else{if(q<=prefix_bound)copy=prefix_edges.data[q];copy[word[q]-'a']=q+1;}}else if constexpr(Width!=0){int stride=Width>0?Width:alphabet;std::copy_n(flat.data()+size_t(q)*stride,stride,flat.data()+size_t(clone)*stride);}else{auto row=to[q];if(row.a&dense_tag){auto copy=dense[row.a&~dense_tag];row.a=dense_tag|uint32_t(dense.size());dense.push_back(copy);}to.push_back(row);}uint32_t tagged=clone;if constexpr(CloneDense)tagged|=uint32_t(std::min(len,255))<<24;link[last]=link[q]=tagged;uint32_t next;while(state_id(next=get<Width,CloneDense>(p,x,clone_base))==q){set<Width,CloneDense>(p,x,tagged,clone_base);current=link[p];p=state_id(current);}link[clone]=state_id(next)==clone?0:next;}}if constexpr(Count)distinct+=last-length(link[last]);}}template<int Width>std::array<int,4>match(std::string_view other)const{int v=0,matched=0,best=0,end_s=0,end_t=0;for(int i=0;i<(int)other.size();i++){unsigned c=(unsigned char)other[i]-unsigned('a');int x=c<26?code[c]:-1;if(x<0){v=matched=0;continue;}while(v&&!get<Width>(v,x)){v=link[v];matched=length(v);}v=get<Width>(v,x);matched=v?matched+1:0;if(matched>best){best=matched;end_s=position(v);end_t=i+1;}}checkpoint("query");return{end_s-best,end_s,end_t-best,end_t};}[[gnu::always_inline]]auto take_suffix_order()&&{dense=decltype(dense){};clone_edges=zero_storage<row>{};prefix_edges=zero_storage<row>{};int size=states();const int n=this->n;auto links=link.data();auto text=word.data();auto clone=clones.data();auto position=[&](int v){return v<=n?v:clone[v-n-1].pos;};auto tagged_length=[&](uint32_t v){int len=v>>24;return len==255?(int(v&id_mask)<=n?int(v&id_mask):clone[(v&id_mask)-n-1].len):len?len:int(v&id_mask);};struct tree_node{uint32_t offset,mask;};zero_storage<tree_node>tree(size+1);zero_storage<int>children(size);uint32_t border=links[n];while((border&id_mask)>unsigned(n)&&tagged_length(border)>prefix_bound)border=links[border&id_mask];int last_branch=std::max(prefix_bound,(border&id_mask)<=unsigned(n)?int(border&id_mask):0);for(int i=1;i<size;i++){int p=links[i]&id_mask,x=text[position(i)-tagged_length(links[i])-1]-'a';tree.data[p].mask|=1U<<x;links[i]=(x<<24)|p;}for(int i=0;i<=last_branch;i++)tree.data[i+1].offset=tree.data[i].offset+std::popcount(tree.data[i].mask);tree.data[n+1].offset=tree.data[last_branch+1].offset;for(int i=n+1;i<size;i++)tree.data[i+1].offset=tree.data[i].offset+std::popcount(tree.data[i].mask);auto scatter=[&](int i,uint32_t entry){int p=links[i]&id_mask,x=unsigned(links[i])>>24;int rank=std::popcount(tree.data[p].mask&((1U<<x)-1));children.data[tree.data[p].offset+rank]=entry;};for(int i=1;i<=last_branch;i++)scatter(i,uint32_t(i)|dense_tag);for(int i=last_branch+1;i<=n;i++)scatter(i,n-i);for(int i=n+1;i<size;i++)scatter(i,(uint32_t(std::popcount(tree.data[i].mask))<<24)|tree.data[i].offset);checkpoint("tree");int top=0,count=0,cursor=tree.data[0].offset,end=tree.data[1].offset;while(true){if(cursor==end){if(!top)break;end=tree.data[--top].mask;cursor=tree.data[--top].mask;continue;}if(end-cursor>=2){uint64_t pair;std::memcpy(&pair,children.data+cursor,sizeof(pair));if(!(pair&0xFF000000FF000000ULL)){std::memcpy(links+count,&pair,sizeof(pair));count+=2;cursor+=2;continue;}}uint32_t entry=children.data[cursor++];if(!(entry>>24)){links[count++]=entry;continue;}int begin,finish;if(entry&dense_tag){int u=entry&id_mask;links[count++]=n-u;begin=tree.data[u].offset;finish=tree.data[u+1].offset;}else{begin=entry&id_mask;finish=begin+(entry>>24);}if(cursor!=end){tree.data[top++].mask=cursor;tree.data[top++].mask=end;}cursor=begin;end=finish;}checkpoint("dfs");link.resize(n);return std::move(link);}};inline auto suffix_array(std::string text){std::ranges::reverse(text);return suffix_automaton(std::move(text),true).take_suffix_order();}}
Back to top page