Submission #403770

#TimeUsernameProblemLanguageResultExecution timeMemory
403770opukittpceno_hhrPalindromes (APIO14_palindrome)C++17
23 / 100
1091 ms3624 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 { int n; string s; int req(int i, int j, int len) { while (len) { if (i < 0 || j >= n) return 0; if (s[i] != s[j]) return 0; i--; j++; len--; } return 1; } void init(string s_) { s = s_; n = (int)s.size(); } } 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) { 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...