cp-algo/structures/eertree.hpp

• View this file on GitHub
• Last update: 2025-12-12 22:29:00+01:00
• Include: #include "cp-algo/structures/eertree.hpp"

Depends on

• cp-algo/util/big_alloc.hpp

Verified with

• Eertree (verify/string/eertree.test.cpp)

Code

#ifndef CP_ALGO_STRUCTURES_EERTREE_HPP
#define CP_ALGO_STRUCTURES_EERTREE_HPP
#include "../util/big_alloc.hpp"
#include <forward_list>
#include <functional>
#include <iostream>
#include <vector>
#include <string>
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.resize(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 {
            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);
            if(!get(last, c)) {
                int u = get(get_link(link[last]), c);
                link[sz] = u;
                par[sz] = last;
                len[sz] = len[last] + 2;
                to[last].emplace_front((sz++ << 8) | c);
            }
            last = get(last, c);
        }
        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:
        big_vector<big_forward_list<int>> to;
        big_vector<int> len, link, par;
        big_string s;
        int n = 1, sz = 2, last = 0;
    };
}
#endif // CP_ALGO_STRUCTURES_EERTREE_HPP

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


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



#include <set>
#include <map>
#include <deque>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <cstddef>
#include <iostream>
#include <generator>
#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);
                madvise(raw, padded, MADV_POPULATE_WRITE);
                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>>;
    template<typename Ref, typename V = void>

    using big_generator = std::generator<Ref, V, big_alloc<std::byte>>;
}

// Deduction guide to make elements_of with big_generator default to big_alloc
namespace std::ranges {
    template<typename Ref, typename V>
    elements_of(cp_algo::big_generator<Ref, V>&&) -> elements_of<cp_algo::big_generator<Ref, V>&&, cp_algo::big_alloc<std::byte>>;
}


#line 5 "cp-algo/structures/eertree.hpp"
#include <functional>
#line 9 "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.resize(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 {
            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);
            if(!get(last, c)) {
                int u = get(get_link(link[last]), c);
                link[sz] = u;
                par[sz] = last;
                len[sz] = len[last] + 2;
                to[last].emplace_front((sz++ << 8) | c);
            }
            last = get(last, c);
        }
        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:
        big_vector<big_forward_list<int>> to;
        big_vector<int> len, link, par;
        big_string s;
        int n = 1, sz = 2, last = 0;
    };
}

#ifndef CP_ALGO_STRUCTURES_EERTREE_HPP
#define CP_ALGO_STRUCTURES_EERTREE_HPP
#include "../util/big_alloc.hpp"
#include <forward_list>
#include <functional>
#include <iostream>
#include <vector>
#include <string>
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.resize(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{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);if(!get(last,c)){int u=get(get_link(link[last]),c);link[sz]=u;par[sz]=last;len[sz]=len[last]+2;to[last].emplace_front((sz++<<8)|c);}last=get(last,c);}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:big_vector<big_forward_list<int>>to;big_vector<int>len,link,par;big_string s;int n=1,sz=2,last=0;};}
#endif

#line 1 "cp-algo/structures/eertree.hpp"
#line 1 "cp-algo/util/big_alloc.hpp"
#include <set>
#include <map>
#include <deque>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <cstddef>
#include <iostream>
#include <generator>
#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);madvise(raw,padded,MADV_POPULATE_WRITE);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>>;template<typename Ref,typename V=void>using big_generator=std::generator<Ref,V,big_alloc<std::byte>>;}namespace std::ranges{template<typename Ref,typename V>elements_of(cp_algo::big_generator<Ref,V>&&)->elements_of<cp_algo::big_generator<Ref,V>&&,cp_algo::big_alloc<std::byte>>;}
#line 5 "cp-algo/structures/eertree.hpp"
#include <functional>
#line 9 "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.resize(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{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);if(!get(last,c)){int u=get(get_link(link[last]),c);link[sz]=u;par[sz]=last;len[sz]=len[last]+2;to[last].emplace_front((sz++<<8)|c);}last=get(last,c);}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:big_vector<big_forward_list<int>>to;big_vector<int>len,link,par;big_string s;int n=1,sz=2,last=0;};}

Back to top page