Submission #344495

#TimeUsernameProblemLanguageResultExecution timeMemory
34449512tqianPalindromes (APIO14_palindrome)C++17
100 / 100
526 ms63636 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; #define FOR(i, a, b) for (int i = (a); i < (b); ++i) #define F0R(i, a) FOR(i,0,a) #define ROF(i, a, b) for (int i = (b) - 1; i >= (a); --i) #define R0F(i, a) ROF(i, 0, a) #define trav(a, x) for (auto& a : x) typedef string str; template<class T> struct RMQ { // floor(log_2(x)) int level(int x) { return 31-__builtin_clz(x); } vector<T> v; vector<vi> jmp; int comb(int a, int b) { // index of min return v[a]==v[b]?min(a,b):(v[a]<v[b]?a:b); } void init(const vector<T>& _v) { v = _v; jmp = {vi(sz(v))}; iota(all(jmp[0]),0); for (int j = 1; 1<<j <= sz(v); ++j) { jmp.pb(vi(sz(v)-(1<<j)+1)); F0R(i,sz(jmp[j])) jmp[j][i] = comb(jmp[j-1][i], jmp[j-1][i+(1<<(j-1))]); } } int index(int l, int r) { // get index of min element assert(l <= r); int d = level(r-l+1); return comb(jmp[d][l],jmp[d][r-(1<<d)+1]); } T query(int l, int r) { return v[index(l,r)]; } }; struct SuffixArray { str S; int N; vi sa, isa, lcp; void init(str _S) { N = sz(S = _S)+1; genSa(); genLcp(); } void genSa() { sa = isa = vi(N); sa[0] = N-1; iota(1+all(sa),0); sort(1+all(sa),[&](int a, int b) { return S[a] < S[b]; }); FOR(i,1,N) { 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) { // currently sorted by first len chars vi s(sa), is(isa), pos(N); iota(all(pos),0); trav(t,s) { int T = t-len; if (T >= 0) sa[pos[isa[T]]++] = T; } FOR(i,1,N) { int a = sa[i-1], b = sa[i]; isa[b] = is[a] == is[b] && is[a+len] == is[b+len] ? isa[a] : i; } } } void genLcp() { // Kasai's Algo lcp = vi(N-1); int h = 0; F0R(b,N-1) { int a = sa[isa[b]-1]; while (a+h < sz(S) && S[a+h] == S[b+h]) h ++; lcp[isa[b]-1] = h; if (h) h--; } R.init(lcp); /// if we cut off first chars of two strings /// with lcp h then remaining portions still have lcp h-1 } RMQ<int> R; int getLCP(int a, int b) { // lcp of suffixes starting at a,b if (a == b) return sz(S)-a; int l = isa[a], r = isa[b]; if (l > r) swap(l,r); return R.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; } struct IntervalJoin { std::vector<int> e; std::vector<std::pair<int, int>> interval; void init(int n) { e = std::vector<int>(n, -1); interval.resize(n); for (int i = 0; i < n; i++) { interval[i].first = interval[i].second = i; } } int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); } bool same_set(int a, int b) { return get(a) == get(b); } int size(int x) { return -e[get(x)]; } bool unite(int x, int y) { x = get(x), y = get(y); if (x == y) return false; if (e[x] > e[y]) std::swap(x, y); interval[x].first = min(interval[x].first, interval[y].first); interval[x].second = max(interval[x].second, interval[y].second); e[x] += e[y]; e[y] = x; return true; } std::pair<int, int> get_interval(int x) { x = get(x); return interval[x]; } }; template <class T> struct BIT { std::vector<T> bit; int n; void init(int n_) { n = n_; bit.resize(n); } void init(std::vector<T>& a) { n = (int) a.size(); a.assign(n, 0); for (int i = 0; i < (int) a.size(); i++) { add(i, a[i]); } } T sum(int r) { T ret = 0; for (; r >= 0; r = (r & (r + 1)) - 1) ret += bit[r]; return ret; } T query(int l, int r) { return sum(r) - sum(l - 1); } void add(int idx, T delta) { for (; idx < n; idx = idx | (idx + 1)) bit[idx] += delta; } }; int main() { cin.tie(0)->sync_with_stdio(0); string s; cin >> s; int n = sz(s); SuffixArray S; S.init(s); vector<int> m = manacher(s); long long ans = 0; for (ll x : m) ans = max(ans, x); { vector<int> pal(n); for (int i = 1; i < n; i++) { pal[i] = m[2 * i - 1] / 2; } IntervalJoin I; I.init(n); vector<vector<int>> bucket(n); vector<vector<int>> gap(n); for (int i = 0; i < n; i++) { bucket[pal[i]].push_back(i); } for (int i = 0; i < n - 1; i++) { int i1 = S.sa[i + 1]; int i2 = S.sa[i + 2]; int val = S.getLCP(i1, i2); gap[val].push_back(i); } BIT<long long> bit; bit.init(n); for (int i = n - 1; i >= 0; i--) { for (int x : bucket[i]) { bit.add(S.isa[x] - 1, 1); // add 1 to a potential location } for (int x : gap[i]) { I.unite(x, x + 1); } for (int x : bucket[i]) { int y = S.isa[x]-1; pi p = I.get_interval(y); int res = bit.query(p.first, p.second); ans = max(ans, 1LL * 2 * i * res); } } } { vector<int> pal(n); for (int i = 0; i < n; i++) { pal[i] = m[2 * i] / 2; } vector<vector<int>> bucket(n); vector<vector<int>> gap(n); for (int i = 0; i < n; i++) { bucket[pal[i]].push_back(i); } for (int i = 0; i < n - 1; i++) { int i1 = S.sa[i + 1]; int i2 = S.sa[i + 2]; int val = S.getLCP(i1, i2); if (val) gap[val - 1].push_back(i); } IntervalJoin I; I.init(n); BIT<long long> bit; bit.init(n); for (int i = n - 1; i >= 0; i--) { for (int x : bucket[i]) { bit.add(S.isa[x] - 1, 1); } for (int x : gap[i]) { I.unite(x, x + 1); } for (int x : bucket[i]) { int y = S.isa[x]-1; pi p = I.get_interval(y); int res = bit.query(p.first, p.second); ans = max(ans, 1LL * (2 * i + 1) * res); } } ; } 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...