제출 #403828

#제출 시각아이디문제언어결과실행 시간메모리
403828opukittpceno_hhr회문 (APIO14_palindrome)C++17
15 / 100
675 ms65180 KiB
#include <iostream> #include <vector> #include <map> #include <set> #include <queue> #include <algorithm> #include <string> #include <cmath> #include <cstdio> #include <iomanip> #include <fstream> #include <cassert> #include <cstring> #include <unordered_set> #include <unordered_map> #include <numeric> #include <ctime> #include <bitset> #include <complex> #include <chrono> #include <random> #include <functional> using namespace std; typedef long long ll; const int N = 3e5 + 7; const int ALP = 26; namespace Hash { const int MOD = 1e9 + 7; const int BASE = 31; int add(int a, int b) { if (a + b < MOD) { return a + b; } return a + b - MOD; } int sub(int a, int b) { if (a >= b) { return a - b; } return a - b + MOD; } int mul(int a, int b) { return 1LL * a * b % MOD; } int n; int pw[N]; int h[N]; int rh[N]; int req(int i, int j, int len) { i = n - 1 - i; int F = sub(rh[i + len], mul(rh[i], pw[len])); int S = sub(h[j + len], mul(h[j], pw[len])); return F == S; } void init(string s) { n = (int)s.size(); pw[0] = 1; for (int i = 0; i < n; i++) { pw[i + 1] = mul(pw[i], BASE); } for (int i = 0; i < n; i++) { h[i + 1] = add(s[i], mul(h[i], BASE)); } reverse(s.begin(), s.end()); for (int i = 0; i < n; i++) { rh[i + 1] = add(s[i], mul(rh[i], BASE)); } reverse(s.begin(), s.end()); } } namespace SparceTable { const int L = 20; int pw[N]; int mn[L][N]; void init(int n, int *a) { for (int i = 0; i < n; i++) { mn[0][i] = a[i]; } for (int i = 0; i + 1 < L; i++) { for (int j = 0; j + 2 * (1 << i) <= n; j++) { mn[i + 1][j] = min(mn[i][j], mn[i][j + (1 << i)]); } } pw[1] = 0; for (int i = 2; i <= n; i++) { pw[i] = pw[i / 2] + 1; } } int get(int l, int r) { int p = pw[r - l]; return min(mn[p][l], mn[p][r - (1 << p)]); } } namespace SuffixArray { int n; string s; int sa[N]; int wr[N]; int cur_class[N]; tuple<int, int, int> tos[N]; tuple<int, int, int> ntos[N]; vector<int> by_sec[N]; int pcnt[N]; void do_sort() { // cerr << "sort " << endl; // for (int i = 0; i < n; i++) { // cerr << get<0>(tos[i]) << ' ' << get<1>(tos[i]) << endl; // } for (int i = 0; i < n; i++) { pcnt[i] = 0; by_sec[i].clear(); } for (int i = 0; i < n; i++) { pcnt[get<0>(tos[i])]++; by_sec[get<2>(tos[i])].push_back(i); } for (int i = 1; i < n; i++) { pcnt[i] += pcnt[i - 1]; } for (int i = 0; i < n; i++) { pcnt[i]--; } for (int p = 0; p < n; p++) { for (auto i : by_sec[p]) { ntos[pcnt[get<0>(tos[i])]] = tos[i]; pcnt[get<0>(tos[i])]--; } } for (int i = 0; i < n; i++) { tos[i] = ntos[i]; } // cerr << "aft " << endl; // for (int i = 0; i < n; i++) { // cerr << get<0>(tos[i]) << ' ' << get<1>(tos[i]) << endl; // } } void build_sa() { s.push_back(0); n++; { vector<char> hv; for (auto c : s) { hv.push_back(c); } sort(hv.begin(), hv.end()); hv.resize(unique(hv.begin(), hv.end()) - hv.begin()); for (int i = 0; i < n; i++) { cur_class[i] = lower_bound(hv.begin(), hv.end(), s[i]) - hv.begin(); } } for (int l = 1; l < n; l *= 2) { for (int i = 0; i < n; i++) { tos[i] = make_tuple(cur_class[i], cur_class[(i + l) % n], i); } do_sort(); int cnt = 0; for (int i = 0; i < n; i++) { cur_class[get<2>(tos[i])] = cnt; if (i + 1 < n) { cnt += (get<0>(tos[i]) != get<0>(tos[i + 1]) || get<1>(tos[i]) != get<1>(tos[i + 1])); } } } n--; for (int i = 0; i < n; i++) { wr[i] = cur_class[i] - 1; } for (int i = 0; i < n; i++) { sa[wr[i]] = i; } } int l[N]; void build_lcp() { for (int i = 0; i < n; i++) { int k = 0; if (i > 0) { k = l[wr[i - 1]]; } k--; k = max(k, 0); int in_l = wr[i]; if (in_l + 1 == n) { l[in_l] = -1; } else { int j = sa[in_l + 1]; while (i + k < n && j + k < n && s[i + k] == s[j + k]) { k++; } l[in_l] = k; } } SparceTable::init(n, l); } int lcp(int i, int j) { if (i == j) { return n - i; } i = wr[i]; j = wr[j]; if (i > j) swap(i, j); return SparceTable::get(i, j); } void init(string s_) { s = s_; n = (int)s.size(); build_sa(); build_lcp(); } } void solve(vector<int> v, int ml, int add, ll &ans) { int n = (int)v.size(); vector<int> l(n); vector<int> r(n); { vector<int> st; for (int i = 0; i < n; i++) { while (!st.empty() && v[st.back()] >= v[i]) { st.pop_back(); } if (st.empty()) { l[i] = -1; } else { l[i] = st.back(); } st.push_back(i); } } { vector<int> st; for (int i = n - 1; i >= 0; i--) { while (!st.empty() && v[st.back()] >= v[i]) { st.pop_back(); } if (st.empty()) { r[i] = n; } else { r[i] = st.back(); } st.push_back(i); } } for (int i = 0; i < n; i++) { ans = max(ans, (ll)(r[i] - l[i]) * (v[i] * ml + add)); } } int cnt[ALP]; signed main() { ios_base::sync_with_stdio(false); cin.tie(0); string s; cin >> s; int n = (int)s.size(); Hash::init(s); SuffixArray::init(s); ll ans = 0; auto cmp = [&](pair<int, int> X, pair<int, int> Y) { int i1, len1, i2, len2; tie(i1, len1) = X; tie(i2, len2) = Y; int sk = SuffixArray::lcp(i1, i2); if (sk >= len1 || sk >= len2) { return len1 < len2; } i1 += sk; i2 += sk; return (i1 == n || s[i1] < s[i2]); }; //single { for (int i = 0; i < n; i++) { cnt[s[i] - 'a']++; ans = max(ans, (ll)cnt[s[i] - 'a']); } } //even { vector<pair<int, int>> ip; for (int i = 0; i < n; i++) { int mx = -1; int l = -1; int r = n +1; while (r - l > 1) { int mid = (r + l) / 2; if (mid <= i && mid + i <= n && Hash::req(i - 1, i, mid)) { l = mid; } else { r = mid; } } mx = l; ans = max(ans, (ll)2 * mx); if (mx != -1) { ip.push_back({i, mx}); } } sort(ip.begin(), ip.end(), cmp); vector<int> val; for (int i = 0; i + 1 < (int)ip.size(); i++) { val.push_back(min({ip[i].second, ip[i + 1].second, SuffixArray::lcp(ip[i].first, ip[i + 1].first)})); } solve(val, 2, 0, ans); } //odd { vector<pair<int, int>> ip; for (int i = 0; i < n; i++) { int mx = -1; int l = -1; int r = n +1; while (r - l > 1) { int mid = (r + l) / 2; if (mid <= i && mid + i + 1 <= n && Hash::req(i - 1, i + 1, mid)) { l = mid; } else { r = mid; } } mx = l; ans = max(ans, (ll)2 * mx + 1); if (mx != -1) { ip.push_back({i, mx + 1}); } } sort(ip.begin(), ip.end(), cmp); vector<int> val; for (int i = 0; i + 1 < (int)ip.size(); i++) { val.push_back(min({ip[i].second, ip[i + 1].second, SuffixArray::lcp(ip[i].first, ip[i + 1].first)})); } solve(val, 2, -1, ans); } cout << ans << endl; }
#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...