string/palindrome_decomposition_dp.hpp

• View this file on GitHub
• Last update: 2024-04-09 15:17:41+09:00
• Include: #include "string/palindrome_decomposition_dp.hpp"
• Link: https://arxiv.org/pdf/1403.2431.pdf
• Link: https://codeforces.com/contest/932/problem/G
• Link: https://codeforces.com/problemset/problem/906/E

Depends on

• string/palindromic_tree.hpp

Verified with

• test/mytest/palindrome_decomposition_dp.test.cpp
• test/yukicoder/465.test.cpp

Code

#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) || (p == 0);
          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;
}

Back to top page