This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod[2] = {ll(1e9 + 7), ll(1e9 + 9)};
const ll base[2] = {ll(727), ll(1e6 + 1)};
const ll N = 3e5 + 10;
string s;
ll n, base_pwr[2][N], inv[2];
ll pwr(ll a, ll b, ll id){
if (b < 0) return 0;
if (b == 0) return 1;
ll val = pwr(a, b / 2, id);
val *= val;
val %= mod[id];
if (b % 2) val *= a;
return val % mod[id];
}
int main(){
for (ll j = 0; j < 2; j ++){
base_pwr[j][0] = 1;
inv[j] = pwr(base[j], mod[j] - 2, j);
for (ll i = 1; i < N; i ++)
base_pwr[j][i] = base_pwr[j][i - 1] * base[j] % mod[j];
}
cin >> s;
n = s.size();
ll ans = 0;
for (ll len = 1; len <= n; len ++){
ll hsh0[2] = {0}, hsh[2] = {0};
unordered_map<ll, ll> cnt;
ll mx_occur = 0;
for (ll i = 0; i < len; i ++){
for (ll j = 0; j < 2; j ++){
hsh[j] = (hsh[j] * base[j] + s[i]) % mod[j];
hsh0[j] = (hsh0[j] + base_pwr[j][i] * s[i]) % mod[j];
}
}
if (hsh[0] == hsh0[0] and hsh[1] == hsh0[1]){
cnt[hsh[0]]++;
mx_occur = 1;
}
for (ll i = 1; i + len - 1 < n; i ++){
for (ll j = 0; j < 2; j ++){
hsh[j] = (hsh[j] - base_pwr[j][len - 1] * s[i - 1]) % mod[j];
hsh[j] = (hsh[j] * base[j] + s[i + len - 1]) % mod[j];
hsh[j] = (hsh[j] + mod[j]) % mod[j];
hsh0[j] = (hsh0[j] - s[i - 1] + mod[j]) % mod[j];
hsh0[j] = (hsh0[j] * inv[j]) % mod[j];
hsh0[j] = (hsh0[j] + base_pwr[j][len - 1] * s[i + len - 1]) % mod[j];
}
if (hsh[0] == hsh0[0] and hsh[1] == hsh0[1]){
cnt[hsh[0]]++;
mx_occur = max(mx_occur, cnt[hsh[0]]);
}
}
ans = max(ans, len * mx_occur);
}
cout << ans << endl;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |