제출 #527867

#제출 시각아이디문제언어결과실행 시간메모리
527867pooyashams회문 (APIO14_palindrome)C++14
0 / 100
705 ms30536 KiB
#pragma GCC diagnostic ignored "-Wmisleading-indentation" // fuck you #include <algorithm> #include <iostream> #include <numeric> #include <cstring> #include <iomanip> #include <vector> #include <bitset> #include <stack> #include <queue> #include <cmath> #include <set> #include <map> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> pii; const int maxn = 6e5+10; const int lgmx = 20; int rnk[lgmx][maxn]; int P[maxn]; char s[maxn]; int f, pw; int sfa[maxn]; int lcpa[maxn]; int L[maxn]; int R[maxn]; int n; inline bool cmp(int i, int j) { return rnk[f-1][i] < rnk[f-1][j] or (rnk[f-1][i] == rnk[f-1][j] and rnk[f-1][i+pw] < rnk[f-1][j+pw]); } inline void suffix_array() { iota(P, P+n, 0); sort(P, P+n, [&](int i, int j){return s[i] < s[j];}); rnk[0][P[0]] = 1; for(int i = 1; i < n; i++) rnk[0][P[i]] = rnk[0][P[i-1]] + (s[P[i]] != s[P[i-1]]); pw = 1; for(f = 1; f < lgmx; f++) { sort(P, P+n, cmp); rnk[f][P[0]] = 1; for(int i = 1; i < n; i++) rnk[f][P[i]] = rnk[f][P[i-1]] + cmp(P[i-1], P[i]); pw *= 2; } } inline int lcp(int i, int j) { if(i == j) return n-i; int m = 0; for(int k = lgmx-1; k >= 0; k--) { if(rnk[k][i+m] == rnk[k][j+m]) m += (1<<k); } return m; } int32_t main() { ios::sync_with_stdio(false); cin.tie(0); cin >> s; n = strlen(s); suffix_array(); ll ans = n; iota(sfa, sfa+n, 0); sort(sfa, sfa+n, [&](int i, int j){return rnk[lgmx-1][i] < rnk[lgmx-1][j];}); for(int i = 1; i < n; i++) lcpa[i] = lcp(sfa[i-1], sfa[i]); lcpa[0] = -1; lcpa[n] = -1; L[0] = 0; R[n] = n; for(int i = 1; i < n; i++) for(L[i] = i-1; lcpa[L[i]] >= lcpa[i]; L[i] = L[L[i]]); for(int i = n-1; i >= 0; i--) for(R[i] = i+1; lcpa[R[i]] > lcpa[i]; R[i] = R[R[i]]); for(int i = 1; i < n; i++) ans = max(ans, 1ll*(R[i]-L[i])*lcpa[i]); 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...