cp-algo/data_structures/eertree.hpp

• View this file on GitHub
• Last update: 2024-07-04 14:30:56+02:00
• Include: #include "cp-algo/data_structures/eertree.hpp"

Depends on

• cp-algo/bump_alloc.hpp

Verified with

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

Code

#ifndef CP_ALGO_DATA_STRUCTURES_EERTREE_HPP
#define CP_ALGO_DATA_STRUCTURES_EERTREE_HPP
#include <forward_list>
#include <functional>
#include <iostream>
#include <vector>
#include <string>
#include "../bump_alloc.hpp"
namespace cp_algo::data_structures {
    template<int sigma = 26, char mch = 'a'>
    struct eertree {
        eertree(size_t q) {
            q += 2;
            s = std::string(q, -1);
            len = par = link = std::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:
        std::vector<std::forward_list<int, bump_alloc<int>>> to;
        std::vector<int> len, link, par;
        std::string s;
        int n = 1, sz = 2, last = 0;
    };
}
#endif // CP_ALGO_DATA_STRUCTURES_EERTREE_HPP

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


#include <forward_list>
#include <functional>
#include <iostream>
#include <vector>
#include <string>
#line 1 "cp-algo/bump_alloc.hpp"


#include <cstddef>
namespace cp_algo {
    char buf[450 << 20] alignas(32);
    size_t buf_ind = sizeof buf;
    template<class T> struct bump_alloc {
        typedef T value_type;
        bump_alloc() {}
        template<class U> bump_alloc(const U&) {}
        T* allocate(size_t n) {
            buf_ind -= n * sizeof(T);
            buf_ind &= 0 - alignof(T);
            return (T*)(buf + buf_ind);
        }
        void deallocate(T*, size_t) {}
    };
}

#line 9 "cp-algo/data_structures/eertree.hpp"
namespace cp_algo::data_structures {
    template<int sigma = 26, char mch = 'a'>
    struct eertree {
        eertree(size_t q) {
            q += 2;
            s = std::string(q, -1);
            len = par = link = std::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:
        std::vector<std::forward_list<int, bump_alloc<int>>> to;
        std::vector<int> len, link, par;
        std::string s;
        int n = 1, sz = 2, last = 0;
    };
}

Back to top page