#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define pb push_back
#define all(a) a.begin(), a.end()
#define sz(a) ((int)a.size())
#ifdef Doludu
template <typename T>
ostream& operator << (ostream &o, vector <T> vec) {
o << "{"; int f = 0;
for (T i : vec) o << (f++ ? " " : "") << i;
return o << "}";
}
void bug__(int c, auto ...a) {
cerr << "\e[1;" << c << "m";
(..., (cerr << a << " "));
cerr << "\e[0m" << endl;
}
#define bug_(c, x...) bug__(c, __LINE__, "[" + string(#x) + "]", x)
#define bug(x...) bug_(32, x)
#define bugv(x...) bug_(36, vector(x))
#define safe bug_(33, "safe")
#else
#define bug(x...) void(0)
#define bugv(x...) void(0)
#define safe void(0)
#endif
const int mod = 998244353, N = 500007, logN = 18, C = 26;
struct PAM {
int ch[N][C], cnt[N], fail[N], len[N], _id;
// 0 -> even root, 1 -> odd root
PAM () { reset(); }
int newnode() {
fill_n(ch[_id], C, 0);
cnt[_id] = fail[_id] = len[_id] = 0;
return _id++;
}
void build(string s) {
int lst = 1;
for (int i = 0; i < sz(s); ++i) {
while (s[i - len[lst] - 1] != s[i])
lst = fail[lst];
if (!ch[lst][s[i] - 'a']) {
int idx = newnode();
len[idx] = len[lst] + 2;
int now = fail[lst];
while (s[i - len[now] - 1] != s[i])
now = fail[now];
fail[idx] = ch[now][s[i] - 'a'];
ch[lst][s[i] - 'a'] = idx;
}
lst = ch[lst][s[i] - 'a'], cnt[lst]++;
}
}
void build_count() {
for (int i = _id - 1; i > 1; --i)
cnt[fail[i]] += cnt[i];
}
void reset() { _id = 0, newnode(), newnode(),
len[0] = 0, fail[0] = 1, len[1] = -1; }
} pam;
int main() {
ios::sync_with_stdio(false), cin.tie(0);
string s;
cin >> s;
pam.build(s);
pam.build_count();
ll ans = 0;
for (int i = 2; i < pam._id; ++i) {
ans = max(ans, 1ll * pam.len[i] * pam.cnt[i]);
}
return ans;
}
# | 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... |