Submission #344466

#TimeUsernameProblemLanguageResultExecution timeMemory
34446612tqianPalindromes (APIO14_palindrome)C++17
0 / 100
337 ms53780 KiB
#include <bits/stdc++.h> using namespace std; #define f1r(i, a, b) for (int i = a; i < b; i++) #define f0r(i, a) f1r(i, 0, a) #define eb emplace_back #define pb push_back #define f first #define s second #define mp make_pair #define sz(x) (int) (x).size() #define all(x) (x).begin(), (x).end() typedef long long ll; typedef vector<int> vi; typedef pair<int, int> pi; typedef vector<pi> vpi; template <class T> struct SparseTable { std::vector<T> v; std::vector<std::vector<int>> jump; int level(int x) { return 31 - __builtin_clz(x); } int comb(int a, int b) { return v[a] == v[b] ? std::min(a, b) : (v[a] < v[b] ? a : b); } void init(const std::vector<T>& _v) { v = _v; jump = {std::vector<int>((int) v.size())}; iota(jump[0].begin(), jump[0].end(), 0); for (int j = 1; (1 << j) <= (int) v.size(); j++) { jump.push_back(std::vector<int>((int) v.size() - (1 << j) + 1)); for (int i = 0; i < (int) jump[j].size(); i++) jump[j][i] = comb(jump[j - 1][i], jump[j - 1][i + (1 << (j - 1))]); } } int index(int l, int r) { assert(l <= r); int d = level(r - l + 1); return comb(jump[d][l], jump[d][r - (1 << d) + 1]); } T query(int l, int r) { return v[index(l, r)]; } }; struct SuffixArray { int n; std::vector<int> sa, isa, lcp; std::string s; SparseTable<int> S; void init(std::string s_) { n = (int) (s = s_).size() + 1; gen_suffix_array(); gen_lcp_array(); } void gen_suffix_array() { sa = isa = std::vector<int>(n); sa[0] = n - 1; iota(1 + sa.begin(), sa.end(), 0); sort(1 + sa.begin(), sa.end(), [&](int a, int b) { return s[a] < s[b]; }); for (int i = 1; i < n; i++) { int a = sa[i - 1], b = sa[i]; isa[b] = i > 1 && s[a] == s[b] ? isa[a] : i; } for (int len = 1; len < n; len *= 2) { std::vector<int> ss(sa), is(isa), pos(n); iota(pos.begin(), pos.end(), 0); for (auto& t : ss) { int tt = t - len; if (tt >= 0) sa[pos[isa[tt]]++] = tt; } for (int i = 1; i < n; i++) { int a = sa[i - 1], b = sa[i]; isa[b] = is[a] == is[b] && is[a + len] == is[b + len] ? isa[a] : i; } } sa.erase(sa.begin()); } void gen_lcp_array() { lcp = std::vector<int>(n - 1); int h = 0; for (int b = 0; b < n - 1; b++) { int a = sa[isa[b]]; while (a + h < (int) s.size() && s[a + h] == s[b + h]) h++; lcp[isa[b] - 1] = h; if (h) h--; } S.init(lcp); } int get_lcp(int a, int b) { if (a == b) return (int) s.size() - a; int l = isa[a], r = isa[b]; if (l > r) std::swap(l, r); return S.query(l, r - 1); } }; std::vector<int> manacher(std::string s) { std::string t = "@"; for (auto& c : s) t += c, t += '#'; t.back() = '&'; std::vector<int> res((int) t.size() - 1); int lo = 0, hi = 0; for (int i = 1; i < (int) t.size() - 1; i++) { if (i != 1) res[i] = std::min(hi - i, res[hi - i + lo]); while (t[i - res[i] - 1] == t[i + res[i] + 1]) res[i]++; if (i + res[i] > hi) lo = i - res[i], hi = i + res[i]; } res.erase(res.begin()); for (int i = 0; i < (int) res.size(); i++) if ((i & 1) == (res[i] & 1)) res[i]++; return res; } ll solve(vi v) { int n = sz(v); SparseTable<int> S; S.init(v); ll ret = 0; f0r(i, n) { int l, r; { int lo = 0; int hi = i; while (hi - lo > 1) { int mid = (lo + hi) / 2; if (S.query(mid, i) == v[i]) hi = mid; else lo = mid + 1; } if (S.query(lo, i) == v[i]) l = lo; else l = hi; } { int lo = i; int hi = n-1; while (hi - lo > 1) { int mid = (lo + hi) / 2; if (S.query(i, mid) == v[i]) lo = mid; else hi = mid - 1; } if (S.query(i, hi) == v[i]) r = hi; else r = lo; } ret = max(ret, 1LL * (r - l + 2) * v[i]); } return ret; } int main() { cin.tie(0)->sync_with_stdio(0); string s; cin >> s; int n = sz(s); SuffixArray S; S.init(s); vi m = manacher(s); ll ans = 0; // take care of palindromes that occur exactly once // We'll consider PAL the 'extension' for (ll x : m) ans = max(ans, x); { // handle even palindromes // even length palindrome // say loc i, len L // consider a contiguous array in suffix array // [l, r] // Say they have lcp of x // min(x, min(PAL [l, r])) * 2 * (r - l + 1) // each thing has in common at most x // and each loc has palinndrome size at most PAL // replace with inner splices, set to min(lcp, PAL[i, i+1]) * 2 // maximize min(l, r) * (r - l + 1) is the new problem? // check the min gap // and bash // okay that works vi pal(n); f0r(i, n) { if (i) pal[i] = m[i*2-1]/2; } vi use(n-1); f0r(i, n-1) { int i1 = S.sa[i]; int i2 = S.sa[i+1]; int val = min(pal[i1], pal[i2]); val = min(S.get_lcp(i, i+1), val); val *= 2; use[i] = val; } ans = max(ans, solve(use)); } { // handle odd palindromes // consider a contiguous array in suffix array // [l, r] // say they have lcp of x // We're considering all of these as the center piece // (min(x - 1, min(PAL [l, r])) * 2 + 1) * (r - l + 1) // replace with inner splices, set to min(lcp - 1, PAL[i, i+1]) * 2 + 1 // maximize min(l, r) * (r - l + 1) // same sub problem vi pal(n); f0r(i, n) { pal[i] = m[2*i] / 2; } vi use(n-1); f0r(i, n-1) { int i1 = S.sa[i]; int i2 = S.sa[i+1]; int val = min(pal[i1], pal[i2]); val = min(val, S.get_lcp(i, i+1)-1); val = 2*val+1; use[i] = val; } ans = max(ans, solve(use)); } cout << ans << '\n'; return 0; }
#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...