Submission #265515

#TimeUsernameProblemLanguageResultExecution timeMemory
265515square1001Palindromes (APIO14_palindrome)C++14
47 / 100
1094 ms18212 KiB
// APIO 2014 Problem 1 - Palindromes #include <string> #include <vector> #include <iostream> #include <algorithm> #include <functional> using namespace std; int main() { // step #1. read input string S; cin >> S; int N = S.size(); // step #2. construct suffix array of T = S + "#" + rev(S) string RS = S; reverse(RS.begin(), RS.end()); string T = S + "#" + RS; vector<int> sa_inv(2 * N + 1); for(int i = 0; i < 2 * N + 1; ++i) { sa_inv[i] = int(T[i]); } for(int i = 1; i < 2 * N + 1; i *= 2) { vector<pair<int, int> > nseq(2 * N + 1); for(int j = 0; j < 2 * N + 1; ++j) { nseq[j] = make_pair(sa_inv[j], j + i < 2 * N + 1 ? sa_inv[j + i] : -1); } vector<pair<int, int> > sseq(nseq); sort(sseq.begin(), sseq.end()); sseq.erase(unique(sseq.begin(), sseq.end()), sseq.end()); for(int j = 0; j < 2 * N + 1; ++j) { sa_inv[j] = lower_bound(sseq.begin(), sseq.end(), nseq[j]) - sseq.begin(); } } vector<int> sa(2 * N + 1); for(int i = 0; i < 2 * N + 1; ++i) { sa[sa_inv[i]] = i; } // step #3. construct rolling-hash table and rolling-hash function const int mod = 469762049; const int base = 311; vector<int> pw(2 * N + 2), h(2 * N + 2); pw[0] = 1; for(int i = 0; i < 2 * N + 1; ++i) { pw[i + 1] = 1LL * pw[i] * base % mod; h[i + 1] = (1LL * h[i] * base + T[i]) % mod; } function<int(int, int)> gethash = [&](int l, int r) { return (h[r] - 1LL * h[l] * pw[r - l] % mod + mod) % mod; }; // step #4. calculate LCP vector<int> lcp(2 * N); for(int i = 0; i < 2 * N; ++i) { int l = 0, r = (2 * N + 1) - max(sa[i], sa[i + 1]) + 1; while(r - l > 1) { int m = (l + r) >> 1; if(gethash(sa[i], sa[i] + m) == gethash(sa[i + 1], sa[i + 1] + m)) l = m; else r = m; } lcp[i] = l; } // step #5. calculate types and lengths of elements in suffix array vector<pair<int, int> > trait(2 * N + 1); for(int i = 0; i < 2 * N + 1; ++i) { if(sa[i] == N) trait[i] = make_pair(0, -1); else if(sa[i] < N) trait[i] = make_pair(1, N - sa[i]); else trait[i] = make_pair(2, (2 * N + 1) - sa[i]); } // step #6. calculate the answer vector<bool> flag(N + 1, false); function<long long(int, int)> solve = [&](int l, int r) { int baselen = trait[l].second; for(int i = l; i < r - 1; ++i) { baselen = min(baselen, lcp[i]); } for(int i = l; i < r; ++i) { if(trait[i].first == 1) { flag[trait[i].second] = true; } } int ct1 = 0, ct2 = 0; for(int i = l; i < r; ++i) { if(trait[i].first == 2) { if(flag[N - trait[i].second]) ++ct1; if(flag[N - trait[i].second + 1]) ++ct2; } } for(int i = l; i < r; ++i) { if(trait[i].first == 1) { flag[trait[i].second] = false; } } long long ans = 0; ans = max(ans, 1LL * (baselen * 2) * ct1); ans = max(ans, 1LL * (baselen * 2 - 1) * ct2); if(r - l > 1) { int pre = l; for(int i = l; i < r; ++i) { if(i == r - 1 || lcp[i] == baselen) { long long res = solve(pre, i + 1); ans = max(ans, res); pre = i + 1; } } } return ans; }; long long ans = solve(1, 2 * N + 1); // step #7. print the answer cout << ans << endl; 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...