This documentation is automatically generated by online-judge-tools/verification-helper
#include "string/double_ended_palindromic_tree.hpp"
// https://arxiv.org/abs/2210.02292
// https://codeforces.com/contest/1738/submission/263034583
template <int sigma, char offset>
struct Double_Ended_Palindromic_Tree {
struct Node {
array<int, sigma> TO; // 両端にある文字を追加してできる回文
int par; // 両端にある文字を除いてできる回文
int link; // longest suffix palindrome ノード
int length; // その回文の長さ
int cnt;
int linkcnt; // suffix link tree での子の個数
// link の計算をメモ化したもの
// str(v)+c の longest palindrome suffix = c+str(w)+c となる w
array<int, sigma> direct_link;
};
static constexpr int ODD = 0, EVEN = 1;
vc<Node> nodes;
vc<int> FREE; // Node が削除済で使われていない index
// 文字列の position ごとに持つもの
struct T {
int c;
// その文字から左右に伸びる極大回文が surface ならばその node
// surface でないならば EVEN
int left_surface, right_surface;
};
int mod, mask;
vc<T> dat;
int L = 0, R = 0; // global index range
int num_node = 0;
int new_node(int par, int link, int length, int c = -1) {
++num_node;
Node n;
fill(all(n.TO), -1);
fill(all(n.direct_link), -1);
n.par = par, n.link = link, n.length = length;
n.linkcnt = n.cnt = 0;
if (link != -1) nodes[link].linkcnt += 1;
int p = 0;
if (FREE.empty()) {
p = len(nodes);
nodes.eb(n);
} else {
p = POP(FREE);
nodes[p] = n;
}
if (par != -1) nodes[par].TO[c] = p;
return p;
}
void remove_node(int nid, int c) {
--num_node;
int pid = nodes[nid].par;
assert(nodes[pid].TO[c] == nid);
nodes[pid].TO[c] = -1;
int k = nodes[nid].link;
nodes[k].linkcnt -= 1;
if (nodes[k].linkcnt == 0) FREE.eb(nid);
}
Double_Ended_Palindromic_Tree(int max_size) { // odd, even
assert(ODD == new_node(-1, -1, -1));
assert(EVEN == new_node(-1, 0, 0));
nodes[ODD].cnt = infty<int>, nodes[EVEN].cnt = infty<int>;
mod = 4;
while (mod < max_size) mod *= 2;
dat.resize(mod);
mask = mod - 1;
}
int suffix_node() {
return (L == R ? EVEN : dat[(R - 1) & mask].left_surface);
}
int prefix_node() { return (L == R ? EVEN : dat[L & mask].right_surface); }
void push_back(int c) {
assert(R - L <= mask);
c -= offset;
int v = suffix_node();
dat[R & mask].c = c;
// update palindromic tree, v <- nxt suffix node
v = [&]() -> int {
auto dfs = [&](auto& dfs, int v) -> int {
// str(v)+c の longest suffix palindrome = c+str(w)+c
int& w = nodes[v].direct_link[c];
if (w != -1) { return w; }
int p = nodes[v].link;
int j = R - 1 - nodes[p].length;
if (L <= j && j <= R && dat[j & mask].c == c) { return w = p; }
return w = dfs(dfs, p);
};
// いまのノードに足せないなら戻る
int j = R - 1 - nodes[v].length;
if (!(L <= j && j <= R && dat[j & mask].c == c)) { v = dfs(dfs, v); }
// c+str(v)+c を作る
if (nodes[v].TO[c] != -1) { return nodes[v].TO[c]; }
int link = (v == ODD ? EVEN : nodes[dfs(dfs, v)].TO[c]);
return new_node(v, link, nodes[v].length + 2, c);
}();
dat[R & mask].right_surface = EVEN;
dat[(R - nodes[v].length + 1) & mask].right_surface = v;
dat[R & mask].left_surface = v;
int w = nodes[v].link;
int k = (R - nodes[v].length + nodes[w].length);
if (nodes[w].length >= 1 && dat[k & mask].left_surface == w) {
dat[k & mask].left_surface = EVEN;
}
++R, nodes[v].cnt += 1;
}
void pop_back() {
assert(L < R);
int v = suffix_node();
int w = nodes[v].link;
int k = R - 1 - nodes[v].length + nodes[w].length;
if (nodes[dat[k & mask].left_surface].length < nodes[w].length) {
dat[k & mask].left_surface = w;
dat[(k - nodes[w].length + 1) & mask].right_surface = w;
} else {
dat[(k - nodes[w].length + 1) & mask].right_surface = EVEN;
}
nodes[v].cnt--;
if (nodes[v].linkcnt == 0 && nodes[v].cnt == 0) {
remove_node(v, dat[(R - 1) & mask].c);
}
--R;
}
void push_front(int c) {
assert(R - L <= mask);
c -= offset;
int v = prefix_node();
dat[(L - 1) & mask].c = c;
// update palindromic tree, v <- nxt suffix node
v = [&]() -> int {
auto dfs = [&](auto& dfs, int v) -> int {
// str(v)+c の longest suffix palindrome = c+str(w)+c
int& w = nodes[v].direct_link[c];
if (w != -1) { return w; }
int p = nodes[v].link;
int j = L + nodes[p].length;
if (L - 1 <= j && j <= R - 1 && dat[j & mask].c == c) { return w = p; }
return w = dfs(dfs, p);
};
// いまのノードに足せないなら戻る
int j = L + nodes[v].length;
if (!(L - 1 <= j && j <= R - 1 && dat[j & mask].c == c)) {
v = dfs(dfs, v);
}
// c+str(v)+c を作る
if (nodes[v].TO[c] != -1) { return nodes[v].TO[c]; }
int link = (v == ODD ? EVEN : nodes[dfs(dfs, v)].TO[c]);
return new_node(v, link, nodes[v].length + 2, c);
}();
dat[(L - 1) & mask].left_surface = EVEN;
dat[(L - 2 + nodes[v].length) & mask].left_surface = v;
dat[(L - 1) & mask].right_surface = v;
int w = nodes[v].link;
int k = ((L - 1) + nodes[v].length - nodes[w].length);
if (nodes[w].length >= 1 && dat[k & mask].right_surface == w) {
dat[k & mask].right_surface = EVEN;
}
--L, nodes[v].cnt += 1;
}
void pop_front() {
assert(L < R);
int v = prefix_node();
int w = nodes[v].link;
int k = L + nodes[v].length - nodes[w].length;
if (nodes[dat[k & mask].right_surface].length < nodes[w].length) {
dat[k & mask].right_surface = w;
dat[(k + nodes[w].length - 1) & mask].left_surface = w;
} else {
dat[(k + nodes[w].length - 1) & mask].left_surface = EVEN;
}
nodes[v].cnt--;
if (nodes[v].linkcnt == 0 && nodes[v].cnt == 0) {
remove_node(v, dat[L & mask].c);
}
++L;
}
int count_distinct_palindrome() { return num_node - 2; }
int maximum_prefix_palindrome() { return nodes[prefix_node()].length; }
int maximum_suffix_palindrome() { return nodes[suffix_node()].length; }
};
#line 1 "string/double_ended_palindromic_tree.hpp"
// https://arxiv.org/abs/2210.02292
// https://codeforces.com/contest/1738/submission/263034583
template <int sigma, char offset>
struct Double_Ended_Palindromic_Tree {
struct Node {
array<int, sigma> TO; // 両端にある文字を追加してできる回文
int par; // 両端にある文字を除いてできる回文
int link; // longest suffix palindrome ノード
int length; // その回文の長さ
int cnt;
int linkcnt; // suffix link tree での子の個数
// link の計算をメモ化したもの
// str(v)+c の longest palindrome suffix = c+str(w)+c となる w
array<int, sigma> direct_link;
};
static constexpr int ODD = 0, EVEN = 1;
vc<Node> nodes;
vc<int> FREE; // Node が削除済で使われていない index
// 文字列の position ごとに持つもの
struct T {
int c;
// その文字から左右に伸びる極大回文が surface ならばその node
// surface でないならば EVEN
int left_surface, right_surface;
};
int mod, mask;
vc<T> dat;
int L = 0, R = 0; // global index range
int num_node = 0;
int new_node(int par, int link, int length, int c = -1) {
++num_node;
Node n;
fill(all(n.TO), -1);
fill(all(n.direct_link), -1);
n.par = par, n.link = link, n.length = length;
n.linkcnt = n.cnt = 0;
if (link != -1) nodes[link].linkcnt += 1;
int p = 0;
if (FREE.empty()) {
p = len(nodes);
nodes.eb(n);
} else {
p = POP(FREE);
nodes[p] = n;
}
if (par != -1) nodes[par].TO[c] = p;
return p;
}
void remove_node(int nid, int c) {
--num_node;
int pid = nodes[nid].par;
assert(nodes[pid].TO[c] == nid);
nodes[pid].TO[c] = -1;
int k = nodes[nid].link;
nodes[k].linkcnt -= 1;
if (nodes[k].linkcnt == 0) FREE.eb(nid);
}
Double_Ended_Palindromic_Tree(int max_size) { // odd, even
assert(ODD == new_node(-1, -1, -1));
assert(EVEN == new_node(-1, 0, 0));
nodes[ODD].cnt = infty<int>, nodes[EVEN].cnt = infty<int>;
mod = 4;
while (mod < max_size) mod *= 2;
dat.resize(mod);
mask = mod - 1;
}
int suffix_node() {
return (L == R ? EVEN : dat[(R - 1) & mask].left_surface);
}
int prefix_node() { return (L == R ? EVEN : dat[L & mask].right_surface); }
void push_back(int c) {
assert(R - L <= mask);
c -= offset;
int v = suffix_node();
dat[R & mask].c = c;
// update palindromic tree, v <- nxt suffix node
v = [&]() -> int {
auto dfs = [&](auto& dfs, int v) -> int {
// str(v)+c の longest suffix palindrome = c+str(w)+c
int& w = nodes[v].direct_link[c];
if (w != -1) { return w; }
int p = nodes[v].link;
int j = R - 1 - nodes[p].length;
if (L <= j && j <= R && dat[j & mask].c == c) { return w = p; }
return w = dfs(dfs, p);
};
// いまのノードに足せないなら戻る
int j = R - 1 - nodes[v].length;
if (!(L <= j && j <= R && dat[j & mask].c == c)) { v = dfs(dfs, v); }
// c+str(v)+c を作る
if (nodes[v].TO[c] != -1) { return nodes[v].TO[c]; }
int link = (v == ODD ? EVEN : nodes[dfs(dfs, v)].TO[c]);
return new_node(v, link, nodes[v].length + 2, c);
}();
dat[R & mask].right_surface = EVEN;
dat[(R - nodes[v].length + 1) & mask].right_surface = v;
dat[R & mask].left_surface = v;
int w = nodes[v].link;
int k = (R - nodes[v].length + nodes[w].length);
if (nodes[w].length >= 1 && dat[k & mask].left_surface == w) {
dat[k & mask].left_surface = EVEN;
}
++R, nodes[v].cnt += 1;
}
void pop_back() {
assert(L < R);
int v = suffix_node();
int w = nodes[v].link;
int k = R - 1 - nodes[v].length + nodes[w].length;
if (nodes[dat[k & mask].left_surface].length < nodes[w].length) {
dat[k & mask].left_surface = w;
dat[(k - nodes[w].length + 1) & mask].right_surface = w;
} else {
dat[(k - nodes[w].length + 1) & mask].right_surface = EVEN;
}
nodes[v].cnt--;
if (nodes[v].linkcnt == 0 && nodes[v].cnt == 0) {
remove_node(v, dat[(R - 1) & mask].c);
}
--R;
}
void push_front(int c) {
assert(R - L <= mask);
c -= offset;
int v = prefix_node();
dat[(L - 1) & mask].c = c;
// update palindromic tree, v <- nxt suffix node
v = [&]() -> int {
auto dfs = [&](auto& dfs, int v) -> int {
// str(v)+c の longest suffix palindrome = c+str(w)+c
int& w = nodes[v].direct_link[c];
if (w != -1) { return w; }
int p = nodes[v].link;
int j = L + nodes[p].length;
if (L - 1 <= j && j <= R - 1 && dat[j & mask].c == c) { return w = p; }
return w = dfs(dfs, p);
};
// いまのノードに足せないなら戻る
int j = L + nodes[v].length;
if (!(L - 1 <= j && j <= R - 1 && dat[j & mask].c == c)) {
v = dfs(dfs, v);
}
// c+str(v)+c を作る
if (nodes[v].TO[c] != -1) { return nodes[v].TO[c]; }
int link = (v == ODD ? EVEN : nodes[dfs(dfs, v)].TO[c]);
return new_node(v, link, nodes[v].length + 2, c);
}();
dat[(L - 1) & mask].left_surface = EVEN;
dat[(L - 2 + nodes[v].length) & mask].left_surface = v;
dat[(L - 1) & mask].right_surface = v;
int w = nodes[v].link;
int k = ((L - 1) + nodes[v].length - nodes[w].length);
if (nodes[w].length >= 1 && dat[k & mask].right_surface == w) {
dat[k & mask].right_surface = EVEN;
}
--L, nodes[v].cnt += 1;
}
void pop_front() {
assert(L < R);
int v = prefix_node();
int w = nodes[v].link;
int k = L + nodes[v].length - nodes[w].length;
if (nodes[dat[k & mask].right_surface].length < nodes[w].length) {
dat[k & mask].right_surface = w;
dat[(k + nodes[w].length - 1) & mask].left_surface = w;
} else {
dat[(k + nodes[w].length - 1) & mask].left_surface = EVEN;
}
nodes[v].cnt--;
if (nodes[v].linkcnt == 0 && nodes[v].cnt == 0) {
remove_node(v, dat[L & mask].c);
}
++L;
}
int count_distinct_palindrome() { return num_node - 2; }
int maximum_prefix_palindrome() { return nodes[prefix_node()].length; }
int maximum_suffix_palindrome() { return nodes[suffix_node()].length; }
};