CP-Algorithms Library
This documentation is automatically generated by competitive-verifier/competitive-verifier
tests/eertree.cpp
- View this file on GitHub
- Last update: 2026-09-10 02:45:56+02:00
Depends on
cp-algo/structures/eertree.hppCode
#include <bits/stdc++.h>
#include <cassert>
#include "cp-algo/structures/eertree.hpp"
using namespace cp_algo::structures;
bool palindrome(std::string const& s) {
return std::equal(s.begin(), s.end(), s.rbegin());
}
void check(std::string const& input) {
eertree tree(input.size());
std::vector<std::string> word(2);
std::set<std::string> distinct;
for(size_t end = 1; end <= input.size(); end++) {
tree.add_letter(input[end - 1]);
std::string longest;
for(size_t begin = 0; begin < end; begin++) {
auto w = input.substr(begin, end - begin);
if(palindrome(w)) {
distinct.insert(w);
if(w.size() > longest.size()) longest = w;
}
}
int id = tree.sufpal();
if(id == (int)word.size()) word.push_back(longest);
assert(id >= 2 && id < (int)word.size() && word[id] == longest);
}
std::ostringstream out;
for(int c: {-256, 256, 257, 511, 1000}) {
assert(tree.get(0, c) == 0 && tree.get(1, c) == 0);
}
auto saved = std::cout.rdbuf(out.rdbuf());
tree.print();
std::cout.rdbuf(saved);
std::istringstream in(out.str());
int count;
in >> count;
assert(count == (int)distinct.size() && count + 2 == (int)word.size());
for(int i = 2; i < count + 2; i++) {
int parent, link;
in >> parent >> link;
if(word[i].size() == 1) assert(parent == 1);
else assert(word[parent] == word[i].substr(1, word[i].size() - 2));
std::string suffix;
for(size_t begin = 1; begin < word[i].size(); begin++) {
auto w = word[i].substr(begin);
if(palindrome(w)) {suffix = w; break;}
}
assert(word[link] == suffix);
}
}
int main() {
check("");
std::mt19937 rng(73159);
for(int t = 0; t < 400; t++) {
int n = 1 + rng() % 80, alphabet = 1 + rng() % 26;
std::string s(n, 'a');
for(char &c: s) c += rng() % alphabet;
check(s);
}
check(std::string(300, 'a'));
std::cout << "402 eertree cases passed brute-force palindrome, parent and suffix-link checks\n";
}
#line 1 "tests/eertree.cpp"
#include <bits/stdc++.h>
#line 1 "cp-algo/structures/eertree.hpp"
#line 1 "cp-algo/util/big_alloc.hpp"
#line 14 "cp-algo/util/big_alloc.hpp"
// 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/structures/stack_union.hpp"
#line 6 "cp-algo/structures/stack_union.hpp"
#include <ranges>
namespace cp_algo::structures {
template<class datatype>
struct stack_union {
stack_union(int n = 0): head(n), next(1), data(1) {}
void push(int v, datatype const& vdata) {
next.push_back(head[v]);
head[v] = (int)std::size(next) - 1;
data.push_back(vdata);
}
template<typename... Args>
void emplace(int v, Args&&... vdata) {
next.push_back(head[v]);
head[v] = (int)std::size(next) - 1;
data.emplace_back(std::forward<Args>(vdata)...);
}
void reserve(int m) {
data.reserve(m);
next.reserve(m);
}
size_t size() const {return std::size(head);}
size_t nodes() const {return std::size(data);}
template<typename Su>
struct _iterator {
using value_type = std::conditional_t<std::is_const_v<Su>, const datatype, datatype>;
using difference_type = std::ptrdiff_t;
Su* su = nullptr;
int sv = 0;
value_type& operator*() const { return su->data[sv]; }
_iterator& operator++() {
sv = su->next[sv];
return *this;
}
_iterator operator++(int) { auto tmp = *this; ++*this; return tmp; }
friend bool operator==(_iterator const& it, std::default_sentinel_t) {
return it.sv == 0;
}
};
using iterator = _iterator<stack_union<datatype>>;
using const_iterator = _iterator<const stack_union<datatype>>;
auto operator[](this auto&& self, int v) {
using Iter = _iterator<std::remove_reference_t<decltype(self)>>;
return std::ranges::subrange(Iter{&self, self.head[v]}, std::default_sentinel);
}
big_vector<int> head, next;
big_vector<datatype> data;
};
}
#line 10 "cp-algo/structures/eertree.hpp"
namespace cp_algo::structures {
template<int sigma = 26, char mch = 'a'>
struct eertree {
eertree(size_t q) {
q += 2;
s = big_string(q, -1);
len = par = link = big_vector(q, 0);
to = stack_union<int>((int)q);
to.reserve((int)q);
link[0] = 1;
len[1] = -1;
}
int get_link(int v) const {
while(s[n - 1] != s[n - len[v] - 2]) {
v = link[v];
}
return v;
}
int get(int v, int c) const {
if(v < 2 && c == char(c)) return root_to[v][(unsigned char)c];
for(int cu: to[v]) {
if(char(cu) == c) {
return cu >> 8;
}
}
return 0;
}
void add_letter(char c) {
c -= 'a';
s[n++] = c;
last = get_link(last);
int v = get(last, c);
if(!v) {
v = sz++;
link[v] = get(get_link(link[last]), c);
par[v] = last;
len[v] = len[last] + 2;
to.push(last, (v << 8) | c);
if(last < 2) root_to[last][(unsigned char)c] = v;
}
last = v;
}
int sufpal(auto &&adjust) const {
return adjust(last);
}
int sufpal() const {
return sufpal(std::identity{});
}
void print(auto &&adjust) const {
std::cout << sz - 2 << "\n";
for(int i = 2; i < sz; i++) {
std::cout << adjust(par[i]) << ' ' << adjust(link[i]) << "\n";
}
}
void print() const {
print(std::identity{});
}
private:
// Cache the two hot roots; other transitions stay in compact lists.
std::array<std::array<int, 256>, 2> root_to{};
stack_union<int> to;
big_vector<int> len, link, par;
big_string s;
int n = 1, sz = 2, last = 0;
};
}
#line 4 "tests/eertree.cpp"
using namespace cp_algo::structures;
bool palindrome(std::string const& s) {
return std::equal(s.begin(), s.end(), s.rbegin());
}
void check(std::string const& input) {
eertree tree(input.size());
std::vector<std::string> word(2);
std::set<std::string> distinct;
for(size_t end = 1; end <= input.size(); end++) {
tree.add_letter(input[end - 1]);
std::string longest;
for(size_t begin = 0; begin < end; begin++) {
auto w = input.substr(begin, end - begin);
if(palindrome(w)) {
distinct.insert(w);
if(w.size() > longest.size()) longest = w;
}
}
int id = tree.sufpal();
if(id == (int)word.size()) word.push_back(longest);
assert(id >= 2 && id < (int)word.size() && word[id] == longest);
}
std::ostringstream out;
for(int c: {-256, 256, 257, 511, 1000}) {
assert(tree.get(0, c) == 0 && tree.get(1, c) == 0);
}
auto saved = std::cout.rdbuf(out.rdbuf());
tree.print();
std::cout.rdbuf(saved);
std::istringstream in(out.str());
int count;
in >> count;
assert(count == (int)distinct.size() && count + 2 == (int)word.size());
for(int i = 2; i < count + 2; i++) {
int parent, link;
in >> parent >> link;
if(word[i].size() == 1) assert(parent == 1);
else assert(word[parent] == word[i].substr(1, word[i].size() - 2));
std::string suffix;
for(size_t begin = 1; begin < word[i].size(); begin++) {
auto w = word[i].substr(begin);
if(palindrome(w)) {suffix = w; break;}
}
assert(word[link] == suffix);
}
}
int main() {
check("");
std::mt19937 rng(73159);
for(int t = 0; t < 400; t++) {
int n = 1 + rng() % 80, alphabet = 1 + rng() % 26;
std::string s(n, 'a');
for(char &c: s) c += rng() % alphabet;
check(s);
}
check(std::string(300, 'a'));
std::cout << "402 eertree cases passed brute-force palindrome, parent and suffix-link checks\n";
}
#line 1 "tests/eertree.cpp"
#include <bits/stdc++.h>
#line 1 "cp-algo/structures/eertree.hpp"
#line 1 "cp-algo/util/big_alloc.hpp"
#line 14 "cp-algo/util/big_alloc.hpp"
#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/structures/stack_union.hpp"
#line 6 "cp-algo/structures/stack_union.hpp"
#include <ranges>
namespace cp_algo::structures{template<class datatype>struct stack_union{stack_union(int n=0):head(n),next(1),data(1){}void push(int v,datatype const&vdata){next.push_back(head[v]);head[v]=(int)std::size(next)-1;data.push_back(vdata);}template<typename... Args>void emplace(int v,Args&&... vdata){next.push_back(head[v]);head[v]=(int)std::size(next)-1;data.emplace_back(std::forward<Args>(vdata)...);}void reserve(int m){data.reserve(m);next.reserve(m);}size_t size()const{return std::size(head);}size_t nodes()const{return std::size(data);}template<typename Su>struct _iterator{using value_type=std::conditional_t<std::is_const_v<Su>,const datatype,datatype>;using difference_type=std::ptrdiff_t;Su*su=nullptr;int sv=0;value_type&operator*()const{return su->data[sv];}_iterator&operator++(){sv=su->next[sv];return*this;}_iterator operator++(int){auto tmp=*this;++*this;return tmp;}friend bool operator==(_iterator const&it,std::default_sentinel_t){return it.sv==0;}};using iterator=_iterator<stack_union<datatype>>;using const_iterator=_iterator<const stack_union<datatype>>;auto operator[](this auto&&self,int v){using Iter=_iterator<std::remove_reference_t<decltype(self)>>;return std::ranges::subrange(Iter{&self,self.head[v]},std::default_sentinel);}big_vector<int>head,next;big_vector<datatype>data;};}
#line 10 "cp-algo/structures/eertree.hpp"
namespace cp_algo::structures{template<int sigma=26,char mch='a'>struct eertree{eertree(size_t q){q+=2;s=big_string(q,-1);len=par=link=big_vector(q,0);to=stack_union<int>((int)q);to.reserve((int)q);link[0]=1;len[1]=-1;}int get_link(int v)const{while(s[n-1]!=s[n-len[v]-2]){v=link[v];}return v;}int get(int v,int c)const{if(v<2&&c==char(c))return root_to[v][(unsigned char)c];for(int cu:to[v]){if(char(cu)==c){return cu>>8;}}return 0;}void add_letter(char c){c-='a';s[n++]=c;last=get_link(last);int v=get(last,c);if(!v){v=sz++;link[v]=get(get_link(link[last]),c);par[v]=last;len[v]=len[last]+2;to.push(last,(v<<8)|c);if(last<2)root_to[last][(unsigned char)c]=v;}last=v;}int sufpal(auto&&adjust)const{return adjust(last);}int sufpal()const{return sufpal(std::identity{});}void print(auto&&adjust)const{std::cout<<sz-2<<"\n";for(int i=2;i<sz;i++){std::cout<<adjust(par[i])<<' '<<adjust(link[i])<<"\n";}}void print()const{print(std::identity{});}private:std::array<std::array<int,256>,2>root_to{};stack_union<int>to;big_vector<int>len,link,par;big_string s;int n=1,sz=2,last=0;};}
#line 4 "tests/eertree.cpp"
using namespace cp_algo::structures;bool palindrome(std::string const&s){return std::equal(s.begin(),s.end(),s.rbegin());}void check(std::string const&input){eertree tree(input.size());std::vector<std::string>word(2);std::set<std::string>distinct;for(size_t end=1;end<=input.size();end++){tree.add_letter(input[end-1]);std::string longest;for(size_t begin=0;begin<end;begin++){auto w=input.substr(begin,end-begin);if(palindrome(w)){distinct.insert(w);if(w.size()>longest.size())longest=w;}}int id=tree.sufpal();if(id==(int)word.size())word.push_back(longest);assert(id>=2&&id<(int)word.size()&&word[id]==longest);}std::ostringstream out;for(int c:{-256,256,257,511,1000}){assert(tree.get(0,c)==0&&tree.get(1,c)==0);}auto saved=std::cout.rdbuf(out.rdbuf());tree.print();std::cout.rdbuf(saved);std::istringstream in(out.str());int count;in>>count;assert(count==(int)distinct.size()&&count+2==(int)word.size());for(int i=2;i<count+2;i++){int parent,link;in>>parent>>link;if(word[i].size()==1)assert(parent==1);else assert(word[parent]==word[i].substr(1,word[i].size()-2));std::string suffix;for(size_t begin=1;begin<word[i].size();begin++){auto w=word[i].substr(begin);if(palindrome(w)){suffix=w;break;}}assert(word[link]==suffix);}}int main(){check("");std::mt19937 rng(73159);for(int t=0;t<400;t++){int n=1+rng()%80,alphabet=1+rng()%26;std::string s(n,'a');for(char&c:s)c+=rng()%alphabet;check(s);}check(std::string(300,'a'));std::cout<<"402 eertree cases passed brute-force palindrome, parent and suffix-link checks\n";}