제출 #403775

#제출 시각아이디문제언어결과실행 시간메모리
403775opukittpceno_hhr회문 (APIO14_palindrome)C++17
23 / 100
1097 ms7208 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; const int INF = 1e9 + 239; 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; string s; vector<int> pw; vector<int> h; vector<int> rh; 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_) { s = s_; n = (int)s.size(); pw.resize(n + 1); h.resize(n + 1); rh.resize(n + 1); 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 SuffixArray { int n; string s; vector<int> sa; vector<int> wr; int lcp(int i, int j) { //TODO int ans = 0; while (i < n && j < n) { if (s[i] != s[j]) { return ans; } ans++; i++; j++; } return ans; } int eq(int i, int j, int len) { return lcp(i, j) >= len; } int cmp(int i, int j) { int sk = lcp(i, j); i += sk; j += sk; if (i == n && j == n) { return 0; } if (i == n || s[i] < s[j]) { return -1; } else { return 1; } } void init(string s_) { s = s_; n = (int)s.size(); for (int i = 0; i < n; i++) { sa.push_back(i); } sort(sa.begin(), sa.end(), [&](int i, int j) { return cmp(i, j) == -1; }); wr.resize(n); for (int i = 0; i < n; i++) { wr[sa[i]] = i; } } } void solve(vector<int> v, int ml, int add, int &ans) { //TODO int n = (int)v.size(); for (int i = 0; i < n; i++) { int mn = INF; for (int j = i; j < n; j++) { mn = min(mn, v[j]); ans = max(ans, (j - i + 2) * (mn * 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); int 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, 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, 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, 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...