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

View this file on GitHub
Last update: 2024-11-12 17:24:17+01:00
Problem: https://judge.yosupo.jp/problem/eertree

Depends on

Code

// @brief Eertree
#define PROBLEM "https://judge.yosupo.jp/problem/eertree"
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("tune=native")
#include "cp-algo/structures/eertree.hpp"
#include <bits/stdc++.h>

using namespace std;
using namespace cp_algo::structures;

int yosupo(int v) {
    if(v == 1) {
        return -1;
    } else if(v > 1) {
        return v - 1;
    } else {
        return 0;
    }
}

void solve() {
    string s;
    cin >> s;
    eertree me(size(s));
    vector<int> lasts;
    lasts.reserve(size(s));
    for(auto c: s) {
        me.add_letter(c);
        lasts.push_back(me.sufpal(yosupo));
    }
    me.print(yosupo);
    ranges::copy(lasts, ostream_iterator<int>(cout, " "));
}

signed main() {
    //freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    while(t--) {
        solve();
    }
}

#line 1 "verify/string/eertree.test.cpp"
// @brief Eertree
#define PROBLEM "https://judge.yosupo.jp/problem/eertree"
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("tune=native")
#line 1 "cp-algo/structures/eertree.hpp"


#include <forward_list>
#include <functional>
#include <iostream>
#include <vector>
#include <string>
#line 1 "cp-algo/util/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/structures/eertree.hpp"
namespace cp_algo::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;
    };
}

#line 6 "verify/string/eertree.test.cpp"
#include <bits/stdc++.h>

using namespace std;
using namespace cp_algo::structures;

int yosupo(int v) {
    if(v == 1) {
        return -1;
    } else if(v > 1) {
        return v - 1;
    } else {
        return 0;
    }
}

void solve() {
    string s;
    cin >> s;
    eertree me(size(s));
    vector<int> lasts;
    lasts.reserve(size(s));
    for(auto c: s) {
        me.add_letter(c);
        lasts.push_back(me.sufpal(yosupo));
    }
    me.print(yosupo);
    ranges::copy(lasts, ostream_iterator<int>(cout, " "));
}

signed main() {
    //freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    while(t--) {
        solve();
    }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	binary_00	AC	122 ms	39 MB
g++	binary_01	AC	137 ms	37 MB
g++	binary_02	AC	120 ms	37 MB
g++	binary_03	AC	128 ms	38 MB
g++	example_00	AC	5 ms	4 MB
g++	example_01	AC	4 ms	4 MB
g++	example_02	AC	4 ms	4 MB
g++	random_00	AC	109 ms	29 MB
g++	random_01	AC	113 ms	29 MB
g++	random_small_sigma_00	AC	164 ms	46 MB
g++	random_small_sigma_01	AC	80 ms	29 MB
g++	random_small_sigma_02	AC	80 ms	29 MB
g++	random_small_sigma_03	AC	83 ms	29 MB
g++	random_small_sigma_04	AC	83 ms	29 MB
g++	short_period_00	AC	178 ms	45 MB
g++	short_period_01	AC	90 ms	25 MB
g++	short_period_02	AC	173 ms	45 MB
g++	short_period_03	AC	88 ms	24 MB
g++	short_period_04	AC	181 ms	45 MB
g++	short_period_05	AC	83 ms	25 MB
g++	short_period_06	AC	171 ms	46 MB
g++	short_period_07	AC	88 ms	25 MB
g++	short_period_08	AC	71 ms	29 MB
g++	short_period_09	AC	40 ms	16 MB