#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fll;
struct eertree {
vector<vector<int>> t;
int n, last, sz;
vector<int> s, len, link, qt;
eertree(int N) {
t = vector<vector<int>>(N+2,vector<int>(26,0));
s = len = link = qt = vector<int>(N+2);
s[0] = -1;
link[0] = 1, len[0] = 0, link[1] = 1, len[1] = -1;
sz = 2, last = 0, n = 1;
}
void add(char c) {
s[n++] = c -= 'a';
while (s[n-len[last]-2] != c) last = link[last];
if (!t[last][c]) {
int prev = link[last];
while (s[n-len[prev]-2] != c) prev = link[prev];
link[sz] = t[prev][c];
len[sz] = len[last]+2;
t[last][c] = sz++;
}
qt[last = t[last][c]]++;
}
int size() { return sz-2; }
ll propagate() {
ll ret = 0;
for (int i = n; i > 1; i--) {
//cout<<link[i]<<'\n';
qt[link[i]] += qt[i];
ret += qt[i];
}
return ret;
}
};
int main() {
ios_base::sync_with_stdio(0);cin.tie(0);
string s; cin >> s;
const int n = s.size();
eertree et(n);
for (char c : s) et.add(c);
et.propagate();
ll ans = 0;
for (int i = 0; i < n + 2; i++) {
ans = max(ans, ((ll) et.qt[i]) * et.len[i]);
}
cout << ans << '\n';
return 0;
}
# | 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... |