string/inverse_manacher.hpp

View this file on GitHub
Last update: 2024-10-11 20:53:53+09:00
Include: #include "string/inverse_manacher.hpp"

Depends on

Verified with

test/5_atcoder/abc349g.test.cpp

Code

#include "ds/unionfind/unionfind.hpp"
#include "other/mex.hpp"

// 各点を中心とする極大回文の長さ (in [1,3,5,...])
// 辞書最小 OR empty
vc<int> inverse_manacher(vc<int> R) {
  for (auto& x: R) assert(x & 1), x = (x + 1) / 2;
  ll N = len(R);
  UnionFind uf(N);
  vvc<int> DIFF(N);
  int i = 0;
  int j = 0;
  while (i < N) {
    while (i >= j && i + j < N) {
      if (R[i] != j) {
        if (j) { uf.merge(i + j, i - j); }
        j += 1;
      } else {
        DIFF[i + j].eb(i - j);
        DIFF[i - j].eb(i + j);
        break;
      }
    }
    if (R[i] != j) return {};
    int k = 1;
    while (i >= k && i + k < N && k + R[i - k] < j) {
      if (R[i + k] != R[i - k]) return {};
      k += 1;
    }
    i += k;
    j -= k;
  }
  vvc<int> vs(N);
  FOR(v, N) vs[uf[v]].eb(v);
  vc<int> ANS(N, -1);
  FOR(v, N) {
    int r = uf[v];
    if (ANS[r] != -1) continue;
    vc<int> tmp;
    for (auto& w: vs[r]) {
      for (auto& to: DIFF[w]) {
        if (ANS[to] != -1) tmp.eb(ANS[to]);
      }
    }
    int x = mex(tmp);
    for (auto& w: vs[r]) ANS[w] = x;
  }
  return ANS;
}

#line 2 "ds/unionfind/unionfind.hpp"

struct UnionFind {
  int n, n_comp;
  vc<int> dat; // par or (-size)
  UnionFind(int n = 0) { build(n); }

  void build(int m) {
    n = m, n_comp = m;
    dat.assign(n, -1);
  }

  void reset() { build(n); }

  int operator[](int x) {
    while (dat[x] >= 0) {
      int pp = dat[dat[x]];
      if (pp < 0) { return dat[x]; }
      x = dat[x] = pp;
    }
    return x;
  }

  ll size(int x) {
    x = (*this)[x];
    return -dat[x];
  }

  bool merge(int x, int y) {
    x = (*this)[x], y = (*this)[y];
    if (x == y) return false;
    if (-dat[x] < -dat[y]) swap(x, y);
    dat[x] += dat[y], dat[y] = x, n_comp--;
    return true;
  }

  vc<int> get_all() {
    vc<int> A(n);
    FOR(i, n) A[i] = (*this)[i];
    return A;
  }
};
#line 1 "other/mex.hpp"
int mex(const vc<int>& A) {
  int n = len(A);
  vc<bool> aru(n + 1);
  for (auto& x: A)
    if (x < n) aru[x] = 1;
  int mex = 0;
  while (aru[mex]) ++mex;
  return mex;
}
#line 3 "string/inverse_manacher.hpp"

// 各点を中心とする極大回文の長さ (in [1,3,5,...])
// 辞書最小 OR empty
vc<int> inverse_manacher(vc<int> R) {
  for (auto& x: R) assert(x & 1), x = (x + 1) / 2;
  ll N = len(R);
  UnionFind uf(N);
  vvc<int> DIFF(N);
  int i = 0;
  int j = 0;
  while (i < N) {
    while (i >= j && i + j < N) {
      if (R[i] != j) {
        if (j) { uf.merge(i + j, i - j); }
        j += 1;
      } else {
        DIFF[i + j].eb(i - j);
        DIFF[i - j].eb(i + j);
        break;
      }
    }
    if (R[i] != j) return {};
    int k = 1;
    while (i >= k && i + k < N && k + R[i - k] < j) {
      if (R[i + k] != R[i - k]) return {};
      k += 1;
    }
    i += k;
    j -= k;
  }
  vvc<int> vs(N);
  FOR(v, N) vs[uf[v]].eb(v);
  vc<int> ANS(N, -1);
  FOR(v, N) {
    int r = uf[v];
    if (ANS[r] != -1) continue;
    vc<int> tmp;
    for (auto& w: vs[r]) {
      for (auto& to: DIFF[w]) {
        if (ANS[to] != -1) tmp.eb(ANS[to]);
      }
    }
    int x = mex(tmp);
    for (auto& w: vs[r]) ANS[w] = x;
  }
  return ANS;
}