回文木(Palindromic Tree)
(string/palindromic_tree.cpp)

• View this file on GitHub
• Last update: 2026-03-08 22:25:54+09:00

説明

文字列の異なる回文部分文字列を管理する eertree である。 1 文字ずつ追加しながら構築でき、全体 $O(NW)$ ではなく遷移参照込みで $O(N)$、固定アルファベットなら実用上ほぼ線形で動く。

できること

• PalindromicTree<W, start> pt 空の palindromic tree を作る
• PalindromicTree<W, start> pt(s) 文字列 s から構築する
• void reserve(int n) 長さ n を見込んで領域を確保する
• int add(char c) 末尾に文字 c を追加し、できた最長回文接尾辞のノード番号を返す
• vector<int> count() 各ノードの出現回数を返す

使い方

根は 2 個あり、0 が長さ -1、1 が長さ 0 を表す。 通常の回文ノードは 2 以降に追加される。 path[i] には prefix s[0..i] の最長回文接尾辞のノード番号が入る。

PalindromicTree<26> pt;
for (char c : s) pt.add(c);

for (int v = 2; v < (int)pt.nodes.size(); ++v) {
    int len = pt.nodes[v].len;
    int link = pt.nodes[v].link;
}

実装上の補足

W はアルファベット数、start は最小文字である。 PalindromicTree<26, 'a'> なら小文字英字用になる。

Verified with

• test/yosupo_eertree.test.cpp

Code

template<int W, char start = 'a'>
struct PalindromicTree {
    struct Node {
        int link;
        int len;
        int first_pos;
        int occ;
        int next[W];

        Node(int link = 0, int len = 0, int first_pos = -1)
            : link(link), len(len), first_pos(first_pos), occ(0) {
            fill(next, next + W, -1);
        }
    };

    vector<Node> nodes;
    vector<int> path;
    string s;
    int last;

    PalindromicTree(): nodes(), path(), s(), last(1) {
        nodes.reserve(2);
        nodes.emplace_back(0, -1, -1);
        nodes.emplace_back(0, 0, -1);
    }

    explicit PalindromicTree(const string &t): PalindromicTree() {
        reserve(t.size());
        build(t);
    }

    void reserve(int n) {
        nodes.reserve(n + 2);
        path.reserve(n);
        s.reserve(n);
    }

    static int ord(char c) {
        return c - start;
    }

    int suffix_link(int v, int pos, int c) const {
        while (true) {
            int j = pos - 1 - nodes[v].len;
            if (j >= 0 && ord(s[j]) == c) return v;
            v = nodes[v].link;
        }
    }

    int add(char ch) {
        int c = ord(ch);
        int pos = s.size();
        s.push_back(ch);

        int p = suffix_link(last, pos, c);
        if (nodes[p].next[c] != -1) {
            last = nodes[p].next[c];
            ++nodes[last].occ;
            path.push_back(last);
            return last;
        }

        int cur = nodes.size();
        nodes.emplace_back(0, nodes[p].len + 2, pos);
        nodes[p].next[c] = cur;
        if (nodes[cur].len == 1) {
            nodes[cur].link = 1;
        } else {
            int q = suffix_link(nodes[p].link, pos, c);
            nodes[cur].link = nodes[q].next[c];
        }
        last = cur;
        ++nodes[last].occ;
        path.push_back(last);
        return last;
    }

    void build(const string &t) {
        for (auto &&c : t) add(c);
    }

    vector<int> count() const {
        vector<int> res(nodes.size());
        for (int i = 0; i < (int)nodes.size(); ++i) res[i] = nodes[i].occ;
        vector<int> ord(nodes.size());
        iota(ord.begin(), ord.end(), 0);
        sort(ord.begin(), ord.end(), [&](int a, int b) { return nodes[a].len > nodes[b].len; });
        for (auto &&v : ord) {
            if (v >= 2) res[nodes[v].link] += res[v];
        }
        return res;
    }
};

/**
 * @brief 回文木(Palindromic Tree)
 */

#line 1 "string/palindromic_tree.cpp"
template<int W, char start = 'a'>
struct PalindromicTree {
    struct Node {
        int link;
        int len;
        int first_pos;
        int occ;
        int next[W];

        Node(int link = 0, int len = 0, int first_pos = -1)
            : link(link), len(len), first_pos(first_pos), occ(0) {
            fill(next, next + W, -1);
        }
    };

    vector<Node> nodes;
    vector<int> path;
    string s;
    int last;

    PalindromicTree(): nodes(), path(), s(), last(1) {
        nodes.reserve(2);
        nodes.emplace_back(0, -1, -1);
        nodes.emplace_back(0, 0, -1);
    }

    explicit PalindromicTree(const string &t): PalindromicTree() {
        reserve(t.size());
        build(t);
    }

    void reserve(int n) {
        nodes.reserve(n + 2);
        path.reserve(n);
        s.reserve(n);
    }

    static int ord(char c) {
        return c - start;
    }

    int suffix_link(int v, int pos, int c) const {
        while (true) {
            int j = pos - 1 - nodes[v].len;
            if (j >= 0 && ord(s[j]) == c) return v;
            v = nodes[v].link;
        }
    }

    int add(char ch) {
        int c = ord(ch);
        int pos = s.size();
        s.push_back(ch);

        int p = suffix_link(last, pos, c);
        if (nodes[p].next[c] != -1) {
            last = nodes[p].next[c];
            ++nodes[last].occ;
            path.push_back(last);
            return last;
        }

        int cur = nodes.size();
        nodes.emplace_back(0, nodes[p].len + 2, pos);
        nodes[p].next[c] = cur;
        if (nodes[cur].len == 1) {
            nodes[cur].link = 1;
        } else {
            int q = suffix_link(nodes[p].link, pos, c);
            nodes[cur].link = nodes[q].next[c];
        }
        last = cur;
        ++nodes[last].occ;
        path.push_back(last);
        return last;
    }

    void build(const string &t) {
        for (auto &&c : t) add(c);
    }

    vector<int> count() const {
        vector<int> res(nodes.size());
        for (int i = 0; i < (int)nodes.size(); ++i) res[i] = nodes[i].occ;
        vector<int> ord(nodes.size());
        iota(ord.begin(), ord.end(), 0);
        sort(ord.begin(), ord.end(), [&](int a, int b) { return nodes[a].len > nodes[b].len; });
        for (auto &&v : ord) {
            if (v >= 2) res[nodes[v].link] += res[v];
        }
        return res;
    }
};

/**
 * @brief 回文木(Palindromic Tree)
 */

Back to top page