Submission #974486

#	Time	Username	Problem	Language	Result	Execution time	Memory
974486		kilkuwu	Palindromes (APIO14_palindrome)	C++17	0 / 100	444 ms	56648 KiB

palindrome

#include <bits/stdc++.h>

#define nl '\n'

#ifdef LOCAL
#include "template/debug.hpp"
#else
#define dbg(...) ;
#define timer(...) ;
#endif

namespace hash {
using u64 = uint64_t;
using u32 = uint32_t;
constexpr int kSeed = -1;  // change this to fixed seed for predictable base
constexpr u64 kAlpha = 1000000007;  // the value is from 0 -> kAlphabet - 1
constexpr u64 kMod = (1ULL << 61) - 1;
static_assert(kMod - kAlpha > 2);
// randomly getting an odd base from kAlpha + 1 -> kMod - 1
u64 get_random_base(u64 not_this = -1) {
  std::mt19937_64 h_rng(
      kSeed == -1
          ? std::chrono::high_resolution_clock::now().time_since_epoch().count()
          : kSeed);
  auto rd = std::uniform_int_distribution<u64>(kAlpha + 2, kMod - 1);
  u64 base = rd(h_rng);
  base -= base % 2 == 0;
  while (base == not_this) {
    base = rd(h_rng);
    base -= base % 2 == 0;
  }
  return base;
}
u64 mul(u64 a, u64 b) {
  u64 l1 = (u32)a, h1 = a >> 32, l2 = (u32)b, h2 = b >> 32;
  u64 l = l1 * l2, m = l1 * h2 + l2 * h1, h = h1 * h2;
  u64 ret = (l & kMod) + (l >> 61) + (h << 3) + (m >> 29) + (m << 35 >> 3) + 1;
  ret = (ret & kMod) + (ret >> 61);
  ret = (ret & kMod) + (ret >> 61);
  return ret - 1;
}
u64 add(u64 a, u64 b) { return a += b, a -= (a >= kMod) * kMod; }
u64 sub(u64 a, u64 b) { return a + (a < b) * kMod - b; }
u64 p = get_random_base(), q = get_random_base(p);
std::vector<u64> pp(1, 1), qq(1, 1);
void ensure_pp_size(int size) {
  while ((int)pp.size() < size) pp.emplace_back(mul(pp.back(), p));
}
void ensure_qq_size(int size) {
  while ((int)qq.size() < size) qq.emplace_back(mul(qq.back(), q));
}
struct FwdHash {
  std::vector<u64> hf;
  FwdHash() = default;
  template <typename String>
  FwdHash(const String& s) : hf(s.size() + 1) {
    ensure_pp_size(s.size() + 1);
    for (int i = 0; i < (int)s.size(); i++) {
      hf[i + 1] = add(mul(hf[i], p), s[i] + 1);
    }
  }
  int size() const { return hf.size() - 1; }
  // NOTE: [l, r)
  u64 get_fwd(int l, int r) const { return sub(hf[r], mul(hf[l], pp[r - l])); }
  int operator[](int index) const { return get_fwd(index, index + 1) - 1; }
};
struct FBHash : FwdHash {
  std::vector<u64> hb;
  FBHash() = default;
  template <typename String>
  FBHash(const String& s) : FwdHash(s), hb(s.size() + 1) {
    for (int i = s.size() - 1; i >= 0; i--) {
      hb[i] = add(mul(hb[i + 1], p), s[i] + 1);
    }
  }
  // NOTE: [l, r)
  u64 get_bwd(int l, int r) const { return sub(hb[l], mul(hb[r], pp[r - l])); }
};
struct Hash2D {
  std::vector<std::vector<u64>> h;
  Hash2D() = default;
  template <typename String2D>
  Hash2D(const String2D& s)
      : h(s.size() + 1, std::vector<u64>(s[0].size() + 1)) {
    int n = s.size();
    int m = s[0].size();
    ensure_pp_size(n + 1);
    ensure_qq_size(m + 1);
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        h[i + 1][j + 1] = add(mul(h[i + 1][j], q), s[i][j] + 1);
      }
    }
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= m; j++) {
        h[i][j] = add(mul(h[i - 1][j], p), h[i][j]);
      }
    }
  }
  // NOTE: [x, u) * [y, v)
  u64 get(int x, int y, int u, int v) {
    auto res = sub(h[u][v], mul(h[x][v], pp[u - x]));
    res = sub(res, mul(h[u][y], qq[v - y]));
    return add(res, mul(mul(h[x][y], pp[u - x]), qq[v - y]));
  }
};
// NOTE: [l1, h1.size()) and [l2, h2.size())
int longest_common_prefix(const FwdHash& h1, const FwdHash& h2, int l1,
                          int l2) {
  int lb = 0, rb = std::min(h1.size() - l1, h2.size() - l2) + 1;
  while (lb < rb - 1) {
    int mb = (lb + rb) / 2;
    if (h1.get_fwd(l1, l1 + mb) == h2.get_fwd(l2, l2 + mb)) {
      lb = mb;
    } else {
      rb = mb;
    }
  }
  return lb;
}
// NOTE: [0, r1) and [0, r2)
int longest_common_suffix(const FwdHash& h1, const FwdHash& h2, int r1,
                          int r2) {
  int lb = 0, rb = std::min(r1, r2) + 1;
  while (lb < rb - 1) {
    int mb = (lb + rb) / 2;
    if (h1.get_fwd(r1 - mb, r1) == h2.get_fwd(r2 - mb, r2)) {
      lb = mb;
    } else {
      rb = mb;
    }
  }
  return lb;
}
// NOTE: [l1, r1) and [l2, r2)
bool is_smaller(const FwdHash& h1, const FwdHash& h2, int l1, int r1, int l2,
                int r2) {
  int lcp = longest_common_prefix(h1, h2, l1, l2);
  int len1 = r1 - l1;
  int len2 = r2 - l2;
  int min_len = std::min(len1, len2);
  return lcp >= min_len ? len1 < len2 : h1[l1 + lcp] < h2[l2 + lcp];
}
}  // namespace hash

using hash::FBHash;
using hash::FwdHash;
using hash::Hash2D;

namespace suffarr {
std::vector<int> sa_is(const std::vector<int> &s, int upper) {
  int n = int(s.size());
  if (n == 0) return {};
  if (n == 1) return {0};
  if (n == 2) {
    if (s[0] < s[1]) {
      return {0, 1};
    } else {
      return {1, 0};
    }
  }

  std::vector<int> sa(n);
  std::vector<bool> ls(n);
  for (int i = n - 2; i >= 0; i--) {
    ls[i] = (s[i] == s[i + 1]) ? ls[i + 1] : (s[i] < s[i + 1]);
  }
  std::vector<int> sum_l(upper + 1), sum_s(upper + 1);
  for (int i = 0; i < n; i++) {
    if (!ls[i]) {
      sum_s[s[i]]++;
    } else {
      sum_l[s[i] + 1]++;
    }
  }
  for (int i = 0; i <= upper; i++) {
    sum_s[i] += sum_l[i];
    if (i < upper) sum_l[i + 1] += sum_s[i];
  }

  auto induce = [&](const std::vector<int> &lms) {
    std::fill(sa.begin(), sa.end(), -1);
    std::vector<int> buf(upper + 1);
    std::copy(sum_s.begin(), sum_s.end(), buf.begin());
    for (auto d : lms) {
      if (d == n) continue;
      sa[buf[s[d]]++] = d;
    }
    std::copy(sum_l.begin(), sum_l.end(), buf.begin());
    sa[buf[s[n - 1]]++] = n - 1;
    for (int i = 0; i < n; i++) {
      int v = sa[i];
      if (v >= 1 && !ls[v - 1]) {
        sa[buf[s[v - 1]]++] = v - 1;
      }
    }
    std::copy(sum_l.begin(), sum_l.end(), buf.begin());
    for (int i = n - 1; i >= 0; i--) {
      int v = sa[i];
      if (v >= 1 && ls[v - 1]) {
        sa[--buf[s[v - 1] + 1]] = v - 1;
      }
    }
  };

  std::vector<int> lms_map(n + 1, -1);
  int m = 0;
  for (int i = 1; i < n; i++) {
    if (!ls[i - 1] && ls[i]) {
      lms_map[i] = m++;
    }
  }
  std::vector<int> lms;
  lms.reserve(m);
  for (int i = 1; i < n; i++) {
    if (!ls[i - 1] && ls[i]) {
      lms.push_back(i);
    }
  }

  induce(lms);

  if (m) {
    std::vector<int> sorted_lms;
    sorted_lms.reserve(m);
    for (int v : sa) {
      if (lms_map[v] != -1) sorted_lms.push_back(v);
    }
    std::vector<int> rec_s(m);
    int rec_upper = 0;
    rec_s[lms_map[sorted_lms[0]]] = 0;
    for (int i = 1; i < m; i++) {
      int l = sorted_lms[i - 1], r = sorted_lms[i];
      int end_l = (lms_map[l] + 1 < m) ? lms[lms_map[l] + 1] : n;
      int end_r = (lms_map[r] + 1 < m) ? lms[lms_map[r] + 1] : n;
      bool same = true;
      if (end_l - l != end_r - r) {
        same = false;
      } else {
        while (l < end_l) {
          if (s[l] != s[r]) {
            break;
          }
          l++;
          r++;
        }
        if (l == n || s[l] != s[r]) same = false;
      }
      if (!same) rec_upper++;
      rec_s[lms_map[sorted_lms[i]]] = rec_upper;
    }

    auto rec_sa = sa_is(rec_s, rec_upper);

    for (int i = 0; i < m; i++) {
      sorted_lms[i] = lms[rec_sa[i]];
    }
    induce(sorted_lms);
  }
  return sa;
}

std::vector<int> suffix_array(const std::vector<int> &s, int upper) {
  assert(0 <= upper);
  for (int d : s) {
    assert(0 <= d && d <= upper);
  }
  auto sa = suffarr::sa_is(s, upper);
  return sa;
}

template <class T>
std::vector<int> suffix_array(const std::vector<T> &s) {
  int n = int(s.size());
  std::vector<int> idx(n);
  iota(idx.begin(), idx.end(), 0);
  sort(idx.begin(), idx.end(), [&](int l, int r) { return s[l] < s[r]; });
  std::vector<int> s2(n);
  int now = 0;
  for (int i = 0; i < n; i++) {
    if (i && s[idx[i - 1]] != s[idx[i]]) now++;
    s2[idx[i]] = now;
  }
  return suffarr::sa_is(s2, now);
}

std::vector<int> suffix_array(const std::string &s) {
  int n = int(s.size());
  std::vector<int> s2(n);
  for (int i = 0; i < n; i++) {
    s2[i] = s[i];
  }
  return suffarr::sa_is(s2, 255);
}

template <class T>
std::vector<int> lcp_array(const std::vector<T> &s,
                           const std::vector<int> &sa) {
  int n = int(s.size());
  assert(n >= 1);
  std::vector<int> rnk(n);
  for (int i = 0; i < n; i++) {
    rnk[sa[i]] = i;
  }
  std::vector<int> lcp(n - 1);
  int h = 0;
  for (int i = 0; i < n; i++) {
    if (h > 0) h--;
    if (rnk[i] == 0) continue;
    int j = sa[rnk[i] - 1];
    for (; j + h < n && i + h < n; h++) {
      if (s[j + h] != s[i + h]) break;
    }
    lcp[rnk[i] - 1] = h;
  }
  return lcp;
}

std::vector<int> lcp_array(const std::string &s, const std::vector<int> &sa) {
  int n = int(s.size());
  std::vector<int> s2(n);
  for (int i = 0; i < n; i++) {
    s2[i] = s[i];
  }
  return lcp_array(s2, sa);
}

// Count keyword occurence in str
// Complexity: O(min(|str|, |keyword|) * lg |str|)
int count_keyword_occurence(const std::string &str,
                            const std::vector<int> &suffarr,
                            const std::string &keyword) {
  const int n = str.size(), m = keyword.size();
  assert(n == (int) suffarr.size());
  if (n < m) return 0;
  auto f1 = [&](int h) {
    for (int j = 0; h + j < n and j < m; j++) {
      if (str[h + j] < keyword[j]) return true;
      if (str[h + j] > keyword[j]) return false;
    }
    return n - h < m;
  };
  auto f2 = [&](int h) {
    for (int j = 0; h + j < n and j < m; j++) {
      // if (str[h + j] < keyword[j]) return true;
      if (str[h + j] > keyword[j]) return false;
    }
    return true;
  };
  const auto L = std::partition_point(suffarr.begin(), suffarr.end(), f1);
  const auto R = std::partition_point(L, suffarr.end(), f2);
  return std::distance(L, R);
  // return std::vector<int>(L, R); // if you need occurence positions
}
}  // namespace suffarr

using suffarr::suffix_array;
using suffarr::lcp_array;

template<typename T, typename F>
struct SparseTable {
  std::vector<std::vector<T>> t;

  SparseTable() {}
  SparseTable(const std::vector<T>& a) : t(std::__lg(a.size()) + 1, std::vector<T>(a)) {
    for (int k = 0; k + 1 < (int) t.size(); k++)
      for (int i = 0; i + (1 << k) < (int) a.size(); i++)
        t[k + 1][i] = F()(t[k][i], t[k][i + (1 << k)]);
  }

  // NOTE: [l, r)
  T query(int l, int r) {
    int k = std::__lg(r - l);
    return F()(t[k][l], t[k][r - (1 << k)]);
  }
};

template<typename T>
struct MinMerge {
  T operator()(const T& a, const T& b) {
    return std::min<T>(a, b);
  }
};


template <typename T>
using MinSparseTable = SparseTable<T, MinMerge<T>>;

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  std::string s;
  std::cin >> s;
  int n = s.size();
  FBHash hasher(s);

  // we get all unique palindromes

  struct Palindrome {
    int m1, m2, len;
  };

  std::set<uint64_t> palin_hashes;
  std::vector<Palindrome> unique_palins;

  auto is_palindrome = [&](int l, int r) -> bool {
    return hasher.get_fwd(l, r) == hasher.get_bwd(l, r);
  };

  auto add_all = [&](int m1, int m2) {
    int lb = 0, rb = std::min(m1 + 1, n - m2) + 1;

    while (lb < rb - 1) {
      int mb = (lb + rb) / 2;
      if (is_palindrome(m1 - mb + 1, m2 + mb)) {
        lb = mb;
      } else {
        rb = mb;
      }
    }

    int len = lb;
    while (len > 0) {
      auto hsh = hasher.get_fwd(m1 - len + 1, m2 + len);
      auto it = palin_hashes.insert(hsh);
      if (it.second == false) break;
      unique_palins.push_back({m1, m2, len});
      len--;
    }
  };

  for (int i = 0; i < n; i++) {
    add_all(i, i);
    if (i + 1 < n) {
      add_all(i, i + 1);
    }
  }

  auto sa = suffix_array(s);
  auto lcp = lcp_array(s, sa);

  dbg(sa);
  dbg(lcp);

  std::vector<int> pos(n);

  for (int i = 0; i < n; i++) {
    pos[sa[i]] = i;
  }

  MinSparseTable<int> tab(lcp);

  auto count_occurrence = [&](int l, int r) -> int {
    int len = r - l;

    l = pos[l];
    int upper = l;
    int lb = 0, rb = l - 1;
    
    while (lb <= rb) {
      int mb = (lb + rb) / 2;
      int val = tab.query(mb, l);
      if (val >= len) {
        upper = mb;
        rb = mb - 1;
      } else {
        lb = mb + 1;
      }
    }

    int lower = l;
    lb = l + 1, rb = n - 1;

    while (lb <= rb) {
      int mb = (lb + rb) / 2;
      int val = tab.query(l, lb);

      if (val >= len) {
        lower = mb;
        lb = mb + 1;
      } else {
        rb = mb - 1;
      }
    }

    dbg(lower, upper);
    return lower - upper + 1;
  };


  int64_t ans = -1;
  for (auto [m1, m2, len] : unique_palins) {
    int lb = m1 - len + 1, rb = m2 + len;
    len = rb - lb;
    dbg(lb, rb);
    ans = std::max(ans, (int64_t) len * count_occurrence(lb, rb));
  }

  std::cout << ans << nl;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 26
• Subtask 5: 0 / 27