string/non_dominated_suffix.hpp

View this file on GitHub
Last update: 2025-05-18 18:12:51+09:00
Include: #include "string/non_dominated_suffix.hpp"

Depends on

Code

#include "string/lyndon.hpp"
#include "string/zalgorithm.hpp"

// suffix X,Y について, Y<X かつ Y notin prefix(X) となる Y がない X たち.
// 長さの列を返す. 互いに border になっている.
// donimate という呼称は見かけはしたけど標準的でない気がする
vc<int> non_dominated_suffix(string S) {
  // Lyndon のところが候補なのだが, どうやって計算しよう.
  // たぶん Duval algo の中を見ればいいんだけど
  // 考えるのが面倒なので Z algorithm で判定してみるか.
  int N = len(S);
  Incremental_Lyndon_Factorization<char> LDN;
  FOR(i, N) LDN.add(S[i]);
  string RS = {S.rbegin(), S.rend()};
  vc<int> Z = zalgorithm(RS);

  vc<int> ANS;
  vc<int> cut = LDN.factorize();
  while (len(cut) >= 2) {
    int r = POP(cut);
    int l = cut.back();
    int n = r - l;
    int m = N - r;
    if (Z[n] < m) break;
    ANS.eb(n + m);
  }
  return ANS;
}

#line 2 "string/lyndon.hpp"

template <typename CHAR>
struct Incremental_Lyndon_Factorization {
  vc<CHAR> S;
  int i = 0, j = 0, k = 0;
  vc<int> minimum_suffix_len = {0};

  int add(CHAR c) {
    S.eb(c);
    // [j, j+(i-k)) simple
    while (i < len(S)) {
      if (k == i) {
        assert(j == k);
        ++i;
      }
      elif (S[k] == S[i]) { ++k, ++i; }
      elif (S[k] < S[i]) { k = j, ++i; }
      else {
        j += (i - j) / (i - k) * (i - k);
        i = k = j;
      }
    }
    if ((i - j) % (i - k) == 0) {
      minimum_suffix_len.eb(i - k);
    } else {
      minimum_suffix_len.eb(minimum_suffix_len[k]);
    }
    return minimum_suffix_len[i];
  }

  vc<int> factorize() {
    int i = len(S);
    vc<int> I;
    while (i) {
      I.eb(i);
      i -= minimum_suffix_len[i];
    }
    I.eb(0);
    reverse(all(I));
    return I;
  }
};
#line 2 "string/zalgorithm.hpp"

template <typename STRING> // string, vector どちらでも
vector<int> zalgorithm(const STRING& s) {
  int n = int(s.size());
  if (n == 0) return {};
  vector<int> z(n);
  z[0] = 0;
  for (int i = 1, j = 0; i < n; i++) {
    int& k = z[i];
    k = (j + z[j] <= i) ? 0 : min(j + z[j] - i, z[i - j]);
    while (i + k < n && s[k] == s[i + k]) k++;
    if (j + z[j] < i + z[i]) j = i;
  }
  z[0] = n;
  return z;
}
#line 3 "string/non_dominated_suffix.hpp"

// suffix X,Y について, Y<X かつ Y notin prefix(X) となる Y がない X たち.
// 長さの列を返す. 互いに border になっている.
// donimate という呼称は見かけはしたけど標準的でない気がする
vc<int> non_dominated_suffix(string S) {
  // Lyndon のところが候補なのだが, どうやって計算しよう.
  // たぶん Duval algo の中を見ればいいんだけど
  // 考えるのが面倒なので Z algorithm で判定してみるか.
  int N = len(S);
  Incremental_Lyndon_Factorization<char> LDN;
  FOR(i, N) LDN.add(S[i]);
  string RS = {S.rbegin(), S.rend()};
  vc<int> Z = zalgorithm(RS);

  vc<int> ANS;
  vc<int> cut = LDN.factorize();
  while (len(cut) >= 2) {
    int r = POP(cut);
    int l = cut.back();
    int n = r - l;
    int m = N - r;
    if (Z[n] < m) break;
    ANS.eb(n + m);
  }
  return ANS;
}