This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub maspypy/library
#include "string/palindrome_decomposition_dp.hpp"
#include "string/palindromic_tree.hpp" /* https://arxiv.org/pdf/1403.2431.pdf 回文に分割する dp は O(nlog n) time, O(n) space になる 同じところに遷移するものをまとめたもの gdp ・dp[i] := dp_init[i] ・F(i, dp[i], gdp[j]): dp[i] に gdp[j] からの遷移を追加 ・gdp[i] := gdp_unit ・G(i, gdp[j], dp[i]): gdp[j] に dp[i] からの遷移をまとめる 偶数長のものに制限してやることもある この場合 i が奇数のときの F は何もしなければよい https://codeforces.com/contest/932/problem/G https://codeforces.com/problemset/problem/906/E */ template <typename DP, typename GDP, typename F1, typename F2> vc<DP> palindrome_decomposition_dp(string S, vc<DP> dp_init, GDP gdp_unit, F1 F, F2 G) { int N = len(S); Palindromic_Tree<26> X(S, 'a'); int n = len(X.nodes); /* 各ノードに対して suffix との長さの差分 同じ差分で何ステップ遡れるか? 遡った先の node */ vc<int> diff(n, infty<int>); vc<int> step(n); vc<int> up(n); FOR(v, 2, n) { int w = X.nodes[v].link; int d = X.nodes[v].length - X.nodes[w].length; diff[v] = d; step[v] = (diff[v] == diff[w] ? step[w] : 0) + 1; up[v] = (diff[v] == diff[w] ? up[w] : w); } vc<DP>& dp = dp_init; assert(len(dp) == N + 1); vc<GDP> gdp(N + 1); auto& path = X.path; FOR(j, 1, N + 1) { int v = path[j]; int i = j - X.nodes[v].length; while (v >= 2) { if (step[v] == 1) { // 1 項だけからなる等差数列の集約で初期化 gdp[i] = gdp_unit; gdp[i] = G(i, gdp[i], dp[i]); } else { // 等差数列の末尾を追加 int idx = i + diff[v] * (step[v] - 1); gdp[i] = G(idx, gdp[i], dp[idx]); } dp[j] = F(j, dp[j], gdp[i]), i += diff[v] * step[v], v = up[v]; } } return dp; }
#line 1 "string/palindromic_tree.hpp" // palindromic tree を作る template <int sigma> struct Palindromic_Tree { struct Node { array<int, sigma> TO; int link; int length; pair<int, int> pos; // position of first ocurrence Node(int link, int length, int l, int r) : link(link), length(length), pos({l, r}) { fill(all(TO), -1); } }; vc<Node> nodes; vc<int> path; template <typename STRING> Palindromic_Tree(const STRING& S, char off) { nodes.eb(Node(-1, -1, 0, -1)); nodes.eb(Node(0, 0, 0, 0)); int p = 0; FOR(i, len(S)) { path.eb(p); int x = S[i] - off; while (p) { int j = i - 1 - nodes[p].length; bool can = (j >= 0 && S[j] - off == x); if (!can) { p = nodes[p].link; continue; } break; } if (nodes[p].TO[x] != -1) { p = nodes[p].TO[x]; continue; } int to = len(nodes); int l = i - 1 - nodes[p].length; int r = i + 1; nodes[p].TO[x] = to; int link; if (p == 0) link = 1; if (p != 0) { while (1) { p = nodes[p].link; int j = i - 1 - nodes[p].length; bool can = (j >= 0 && S[j] - off == x); if (can) break; } assert(nodes[p].TO[x] != -1); link = nodes[p].TO[x]; } nodes.eb(Node(link, r - l, l, r)); p = to; } path.eb(p); } // node ごとの出現回数 vc<int> count() { vc<int> res(len(nodes)); for (auto&& p: path) res[p]++; FOR_R(k, 1, len(nodes)) { int link = nodes[k].link; res[link] += res[k]; } return res; } }; #line 2 "string/palindrome_decomposition_dp.hpp" /* https://arxiv.org/pdf/1403.2431.pdf 回文に分割する dp は O(nlog n) time, O(n) space になる 同じところに遷移するものをまとめたもの gdp ・dp[i] := dp_init[i] ・F(i, dp[i], gdp[j]): dp[i] に gdp[j] からの遷移を追加 ・gdp[i] := gdp_unit ・G(i, gdp[j], dp[i]): gdp[j] に dp[i] からの遷移をまとめる 偶数長のものに制限してやることもある この場合 i が奇数のときの F は何もしなければよい https://codeforces.com/contest/932/problem/G https://codeforces.com/problemset/problem/906/E */ template <typename DP, typename GDP, typename F1, typename F2> vc<DP> palindrome_decomposition_dp(string S, vc<DP> dp_init, GDP gdp_unit, F1 F, F2 G) { int N = len(S); Palindromic_Tree<26> X(S, 'a'); int n = len(X.nodes); /* 各ノードに対して suffix との長さの差分 同じ差分で何ステップ遡れるか? 遡った先の node */ vc<int> diff(n, infty<int>); vc<int> step(n); vc<int> up(n); FOR(v, 2, n) { int w = X.nodes[v].link; int d = X.nodes[v].length - X.nodes[w].length; diff[v] = d; step[v] = (diff[v] == diff[w] ? step[w] : 0) + 1; up[v] = (diff[v] == diff[w] ? up[w] : w); } vc<DP>& dp = dp_init; assert(len(dp) == N + 1); vc<GDP> gdp(N + 1); auto& path = X.path; FOR(j, 1, N + 1) { int v = path[j]; int i = j - X.nodes[v].length; while (v >= 2) { if (step[v] == 1) { // 1 項だけからなる等差数列の集約で初期化 gdp[i] = gdp_unit; gdp[i] = G(i, gdp[i], dp[i]); } else { // 等差数列の末尾を追加 int idx = i + diff[v] * (step[v] - 1); gdp[i] = G(idx, gdp[i], dp[idx]); } dp[j] = F(j, dp[j], gdp[i]), i += diff[v] * step[v], v = up[v]; } } return dp; }