Submission #798220

#TimeUsernameProblemLanguageResultExecution timeMemory
798220alittlemiddlePalindromes (APIO14_palindrome)C++14
0 / 100
10 ms6624 KiB
#include <bits/stdc++.h> #define el '\n' #define fi first #define sc second //#define int ll #define pii pair<int, int> #define all(v) v.begin(), v.end() using namespace std; using ll=long long; using ull=unsigned long long; using ld=long double; const int mod=1e9+7; const int N=2e6+11; int d1[N], d2[N], tmp[N]; string s; void manacher1(string s, int* p) { int n=s.length(); s = "<"+s+">"; int l=0, r=1; for(int i=1; i<=n; i++) { if(i>r) p[i]=0; else p[i]=min(r-i, p[l+r-i]); while(1<=i-p[i] && i+p[i]<=n && s[i-p[i]]==s[i+p[i]]) p[i]++; // mo rong p[i] p[i]--; // bo tam if(i+p[i]>r) { l=i-p[i]; r=i+p[i]; } } } void manacher2(string s, int* p) { int n = s.length(); string s1 = ""; for(char v: s) s1 += '.', s1 += v; s1 += '.'; manacher1(s1, tmp); for(int i=1; i<=n; i++) p[i] = tmp[i*2-1]/2; } void sol() { cin >> s; int n=s.length(); manacher1(s, d1); manacher2(s, d2); s=" "+s; int l=-1, r=-1; int c1, c2; for (int i=1; i<=n; i++) { c1 = i-d1[i]; c2 = i+d1[i]; if (c2-c1+1 > r-l+1) l = c1, r = c2; c1 = i-d2[i]; c2 = i+d2[i]-1; if (c1>=1 && c2<=n && c1<=c2 && c2-c1+1 > r-l+1) l=c1, r=c2; } cout << r-l+1; } signed main() { // freopen("divisor.INP", "r", stdin); // freopen("divisor.OUT", "w", stdout); ios_base::sync_with_stdio(0); cin.tie(0); int t=1; //cin >> t; while(t--) { sol(); } }
#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...