This documentation is automatically generated by competitive-verifier/competitive-verifier
#include "cp-algo/structures/suffix_automaton.hpp"#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 © = 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>
#line 13 "cp-algo/util/big_alloc.hpp"
#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::has_single_bit(Align), "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;
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 © = 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©=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>
#line 13 "cp-algo/util/big_alloc.hpp"
#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::has_single_bit(Align),"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; 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©=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(); } }