Submission #516789

#TimeUsernameProblemLanguageResultExecution timeMemory
516789shrimbPalindromes (APIO14_palindrome)C++17
47 / 100
1068 ms8040 KiB
#include"bits/stdc++.h" using namespace std; #define int long long #define endl '\n' const int mod = 1e9 + 7; const int smolp = 31; string s; int n; int pref[300001]; int suff[300001]; int inv[300001]; int pw (int a, int b) { if (b == 0) return 1; if (b == 1) return a; if (b & 1) return (a * pw(a, b - 1)) % mod; int y = pw(a, b / 2); return (y*y)%mod; } int Solve (int sz) { map<int,int>f; int mxf = 0; for (int i = sz - 1 ; i < n ; i++) { int sub = pref[i] - (i - sz < 0 ? 0 : pref[i-sz]); if (sub < 0) sub += mod; sub *= inv[i - sz + 1]; sub %= mod; int sub2 = suff[i-sz+1] - (i < n - 1 ? suff[i + 1] : 0); if (sub2 < 0) sub2 += mod; sub2 *= inv[(n-1) - i]; sub2 %= mod; // cerr << sz << ": " << sub << " " << sub2 << endl; if (sub == sub2) mxf = max(mxf, ++f[sub]); } return mxf; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cin >> s; n = s.size(); int x = 1; for (int i = 0 ; i <= n ; i++) { inv[i] = pw(x, mod - 2); x *= smolp;x%=mod; } int pp = 1; for (int i = 0 ; i < n ; i++) { int prev_p = (i ? pref[i-1] : 0); pref[i] = prev_p + ((pp * (s[i]-'a'))%mod); pref[i] %= mod; pp *= smolp; pp %= mod; } pp = 1; for (int i = n - 1 ; i >= 0 ; i--) { int prev_s = (i < n - 1 ? suff[i + 1] : 0); suff[i] = prev_s + ((pp * (s[i] - 'a')) % mod); suff[i] %= mod; pp *= smolp; pp %= mod; } int mx_ans = 0; for (int i = 1 ; i <= n ; i++) { // cerr << i << " " << Solve(i) << endl; mx_ans = max(mx_ans, Solve(i) * i); } cout << mx_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...