Submission #677959

#TimeUsernameProblemLanguageResultExecution timeMemory
677959RomirosPalindromes (APIO14_palindrome)C++17
0 / 100
164 ms19104 KiB
#include <bits/stdc++.h> #define ll long long #define ld long double #define vi vector<int> #define pii pair<int, int> #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #pragma GCC optimize("O3", "unroll-loops") #pragma GCC target("avx2", "popcnt") using namespace std; const int MAXN = 3e5 + 10; inline vector<int> build_sa(string s){ int n = s.size(); vector<int> a(n); vector<int> eq(2 * n + 1); vector<int> nw(2 * n + 1); vector<int> t(n + 2); vector<int> nw_a(n); for (int i = 0; i < n; i++){ a[i] = i; } sort(a.begin(), a.end(), [&](int x, int y){ if (s[x] != s[y]){ return s[x] < s[y]; } return x < y; }); eq[a[0]] = 0; for (int i = 1; i < n; i++){ eq[a[i]] = eq[a[i - 1]]; if (s[a[i]] != s[a[i - 1]]){ eq[a[i]]++; } } for (int k = 0; (1 << k) < n; k++){ for (int f = 1; f >= 1; f--){ t.assign(n + 2, 0); for (int i = 0; i < n; i++){ int j = (a[i] - (f << k) + n) % n; // if (eq[j] + 1 < t.size()){ t[eq[j]]++; // } } for (int i = 1; i <= n; i++){ t[i] += t[i - 1]; } // for (int i = n; i >= 1; i--){ // t[i] = t[i - 1]; // } for (int i = n - 1; i >= 0; i--){ int j = (a[i] - (f << k) + n) % n; nw_a[--t[eq[j]]] = a[i]; } nw_a.swap(a); } nw[a[0]] = 1; for (int i = 1; i < n; i++){ int p = a[i]; int q = a[i - 1]; nw[p] = nw[q]; if (eq[p] != eq[q] || eq[p + (1 << k)] != eq[q + (1 << k)]){ nw[p]++; } } nw.swap(eq); } a.insert(a.begin(), n); return a; } inline vector<int> build_lcp(const vector<int>& p, const string& s){ int n = s.size(); vector<int> pos(n + 1); for (int i = 0; i <= n; i++){ pos[p[i]] = i; } vector<int> lcp(n); int k = 0; for (int i = 0; i < (n - 1); i++){ while (s[i + k] == s[p[pos[i] - 1] + k]){ k++; } lcp[pos[i] - 1] = k; k -= (k != 0); } return lcp; } struct SparseTable{ vector<vector<int>> st; SparseTable(vector<int> a){ int n = a.size(); st.resize(n); for (int i = 0; i < n; i++){ st[i].push_back(a[i]); } for (int k = 1; k <= n; k *= 2){ for (int i = 0; i + k < n; i++){ st[i].push_back(min(st[i].back(), st[i + k].back())); } } } inline int log2(int x){ return 31 - __builtin_clz(x); } inline int get(int l, int r){ if (l > r){ return 1e9; } int k = log2(r - l + 1); return min(st[l][k], st[r - (1 << k) + 1][k]); } }; SparseTable sp({}); vector<int> d(MAXN); vector<int> pos; string s; inline int lcp(int i, int j){ int l = pos[i]; int r = pos[j]; if (l > r){ swap(l, r); } return min({d[i], d[j], sp.get(l, r - 1)}); } inline int cmp(int i, int j){ int l = lcp(i, j); if (l == min(d[i], d[j])){ return d[i] < d[j]; } return s[i - l] < s[j - l]; } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); #ifdef ON_PC freopen("input.txt", "r", stdin); #endif // freopen("output.txt", "w", stdout); int T = 1; // cin >> T; while (T--){ cin >> s; int n = s.size(); vector<int> sa = build_sa(s); vector<int> lcpv = build_lcp(sa, s); pos = vector<int>(n + 2); for (int i = 0; i < sa.size(); i++){ pos[sa[i] + 1] = i; } sp = SparseTable(lcpv); s = " " + s; ll res = 0; vector<int> order(n); vector<int> lb(n); vector<int> rb(n); vector<int> st; vector<int> lcp_res(n); for (int f = 0; f < 2; f++){ d.assign(n + 1, 0); for (int i = 1, l = 0, r = -1; i <= n; i++){ if (i + f <= r){ d[i] = min(r - (i + f) + 1, d[l + r - (i + f)]); } while (i - d[i] >= 1 && i + f + d[i] <= n && s[i - d[i]] == s[i + f + d[i]]){ d[i]++; } if (i + f + d[i] - 1 > r){ r = i + f + d[i] - 1; l = i - d[i] + 1; } } for (int i = 1; i <= n; i++){ res = max(res, (ll)(2 * d[i] - !f)); } for (int i = 1; i <= n; i++){ order[i - 1] = i; } sort(all(order), cmp); for (int i = 0; i + 1 < n; i++){ lcp_res[i] = lcp(order[i], order[i + 1]); } for (int i = 0; i < n; i++){ while (!st.empty() && lcp_res[st.back()] >= lcp_res[i]){ st.pop_back(); } lb[i] = 0; if (!st.empty()){ lb[i] = st.back() + 1; } st.push_back(i); } st.clear(); for (int i = n - 1; i >= 0; i--){ while (!st.empty() && lcp_res[st.back()] >= lcp_res[i]){ st.pop_back(); } rb[i] = n - 1; if (!st.empty()){ rb[i] = st.back(); } st.push_back(i); } st.clear(); for (int i = 0; i < n; i++){ res = max(res, (2 * lcp_res[i] - !f) * 1ll * (rb[i] - lb[i] + 1)); } } cout << res << "\n"; } return 0; }

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:161:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  161 |         for (int i = 0; i < sa.size(); i++){
      |                         ~~^~~~~~~~~~~
#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...