#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
using namespace std;
const int N = 1e4 + 10, p = 2e7 + 33;
int n, h1[N], h2[N], pw[N], cnt[p];
string s;
int mul(int a, int b) {
return 1ll * a * b % p;
}
int sum(int a, int b) {
a += b;
if (a < 0) a += p;
if (a >= p) a -= p;
return a;
}
int get1(int l, int r) {
int res = h1[r];
res = sum(res, -mul(pw[r - l], h1[l]));
return res;
}
int get2(int l, int r) {
int res = h2[l];
res = sum(res, -mul(pw[r - l], h2[r]));
return res;
}
void input() {
cin >> s;
n = s.size();
}
void solve() {
pw[0] = 1;
for (int i = 1; i < N; i++)
pw[i] = mul(pw[i - 1], 28);
for (int i = 0; i < n; i++) {
h1[i + 1] = mul(h1[i], 28);
h1[i + 1] = sum(h1[i + 1], s[i] - 'a' + 1);
}
for (int i = n - 1; i >= 0; i--) {
h2[i] = mul(h2[i + 1], 28);
h2[i] = sum(h2[i], s[i] - 'a' + 1);
}
int ans = 0;
for (int len = 1; len <= n && len * (n - len + 1) > ans; len++) {
for (int i = 0; i + len <= n; i++) {
int j = i + len;
if (get1(i, j) == get2(i, j)) {
int tmp = get1(i, j);
cnt[tmp] += j - i;
ans = max(ans, cnt[tmp]);
}
}
}
cout << ans;
}
int main() {
ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
input();
solve();
}
# | 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... |