제출 #46675

#제출 시각아이디문제언어결과실행 시간메모리
46675minkank회문 (APIO14_palindrome)C++17
0 / 100
503 ms47976 KiB
#include <bits/stdc++.h> #define ll long long using namespace std; const ll mod = (ll) 1e9+9; const ll base = 29; int lg2[300005]; void prepLg2(int bound){ for(int i=2;i<=bound;i++) lg2[i] = lg2[i>>1] + 1; } struct suffixArray{ vector <int> sa, saRank, tmp; vector <vector <int> > lcp; int strLen, gap; bool saCmp(int x,int y){ if (saRank[x] != saRank[y]) return saRank[x] < saRank[y]; return x+gap < strLen && y+gap < strLen ? saRank[x+gap] < saRank[y+gap] : x > y; } void build_lcp(string &s){ int k = 0; for(int i = 0; i < strLen; i ++){ if (saRank[i] != strLen - 1){ for (int j = sa[saRank[i] + 1]; max(i+k, j+k) < strLen && s[i + k] == s[j + k];) ++k; lcp[saRank[i]][0] = k; if (k) k--; } } for(int k = 1; k < 20; k ++){ for(int i = 0; i < strLen; i ++) if (i + (1<<k) < strLen) lcp[i][k] = min(lcp[i][k-1], lcp[i+(1<<(k-1))][k-1]); else break; } } int getLcp(int l,int r){ if (l > r) swap(l, r); if (l == r) return strLen - sa[l]; int k = lg2[r - l]; return min(lcp[l][k], lcp[r-(1<<k)][k]); } void build(string &s, int isIndexFromOne = 0){ strLen = s.size(); sa.assign(strLen + 5, 0); saRank.assign(strLen + 5, 0); tmp.assign(strLen + 5, 0); lcp.assign(strLen + 5, vector<int>(20)); //for(int i = 0; i < strLen; i ++) // lcp[i].assign(20, 0); for(int i = 0; i < strLen; i ++) sa[i] = i, saRank[i] = s[i]; for(gap = 1;;gap *= 2){ sort(sa.begin(), sa.begin() + strLen, [&](int a, int b) {return this->saCmp(a, b);}); //sort(sa.begin(), sa.begin() + strLen, saCmp); for(int i = 0; i < strLen; i ++) tmp[i+1] = tmp[i] + saCmp(sa[i], sa[i+1]); for(int i = 0; i < strLen; i ++) saRank[sa[i]] = tmp[i]; if (tmp[strLen-1] == strLen-1) break; } build_lcp(s); } }; int n; string s[2]; suffixArray suff; ll hashCode[2][300000], pBase[300000]; void prepHash(){ pBase[0] = 1; for(int i=1;i<300000;i++) pBase[i] = pBase[i-1] * base % mod; hashCode[0][0] = s[0][0] - 'a' + 1; hashCode[1][0] = s[1][0] - 'a' + 1; for(int i=1;i<n;i++) hashCode[0][i] = (hashCode[0][i-1] + pBase[i] * (s[0][i] - 'a' + 1)) % mod, hashCode[1][i] = (hashCode[1][i-1] + pBase[i] * (s[1][i] - 'a' + 1)) % mod; } bool checkPalindrome(int l1,int r1){ int l2 = n-1-r1; int r2 = n-1-l1; ll val1 = (hashCode[0][r1] - (l1 == 0 ? 0 : hashCode[0][l1-1]) + mod) % mod; ll val2 = (hashCode[1][r2] - (l2 == 0 ? 0 : hashCode[1][l2-1]) + mod) % mod; val1 = val1 * pBase[max(0, r2 - r1)] % mod; val2 = val2 * pBase[max(0, r1 - r2)] % mod; return val1 == val2; } long long solve(int p, int sz) { int id = suff.saRank[p]; int l = id; //cout << p << ' ' << sz << endl; for(int i = 19; i >= 0; --i) { int cur = l - (1 << i); if(cur < 0) continue; if(suff.lcp[cur][i] >= sz) l = cur; } int r = id; for(int i = 19; i >= 0; --i) { if(suff.lcp[r][i] >= sz) r = min(n - 1, r + (1 << i)); } return 1LL * sz * (r - l + 1); } int main(){ prepLg2(300000); iostream::sync_with_stdio(0); cin >> s[0]; n = s[0].size(); s[1] = s[0]; reverse(s[1].begin(), s[1].end()); suff.build(s[0]); prepHash(); /* int sz0, sz1; sz0 = 0, sz1 = 1; long long ans = 0; for(int i = n - 1; i >= 0; --i) { int p0 = i + 2 * sz0 - 1; int p1 = i + 2 * sz1 - 2; if(p0 >= i) ans = max(ans, solve(i, p0 - i + 1)); if(p1 >= i) ans = max(ans, solve(i, p1 - i + 1)); if(i == 0) continue; sz0++, sz1++; while(sz0) { p0 = i - 1 + 2 * sz0 - 1; if(!checkPalindrome(i - 1, p0)) sz0--; else break; } while(sz1) { p1 = i - 1 + 2 * sz1 - 2; if(!checkPalindrome(i - 1, p1)) sz1--; else break; } } cout << ans; */ }
#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...