제출 #974493

#제출 시각아이디문제언어결과실행 시간메모리
974493kilkuwu회문 (APIO14_palindrome)C++17
100 / 100
527 ms57892 KiB
#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); std::vector<int> pos(n); for (int i = 0; i < n; i++) { pos[sa[i]] = i; } MinSparseTable<int> tab(lcp); dbg(sa); dbg(lcp); /* 2 bbbc 1 bbc 0 bc c */ 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, mb); if (val >= len) { lower = mb; lb = mb + 1; } else { rb = mb - 1; } } dbg(lower, upper); return lower - upper + 1; }; // b, b, b, c 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...