# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
551614 | hoanghq2004 | Palindromes (APIO14_palindrome) | C++14 | 24 ms | 36272 KiB |
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>
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 3e5 + 10;
int nNode, suff;
string s;
struct node {
int nxt[26];
int len, link;
} Tree[N];
void init() {
nNode = 1, suff = 1;
Tree[0].len = -1;
Tree[1].len = 0;
}
void add(int i) {
int cur = suff;
while (1) {
int curlen = Tree[cur].len;
if (s[i] == s[i - curlen - 1]) break;
cur = Tree[cur].link;
}
if (Tree[cur].nxt[s[i] - 'a']) {
suff = Tree[cur].nxt[s[i] - 'a'];
return;
}
suff = ++nNode;
Tree[cur].nxt[s[i] - 'a'] = suff;
Tree[suff].len = Tree[cur].len + 2;
if (Tree[suff].len == 1) {
Tree[suff].link = 1;
return;
}
while (1) {
cur = Tree[cur].link;
int curlen = Tree[cur].len;
if (s[i] == s[i - curlen - 1]) break;
}
Tree[suff].link = Tree[cur].nxt[s[i] - 'a'];
}
long long cnt[N];
int main() {
ios :: sync_with_stdio(0); cin.tie(0);
cin >> s;
init();
for (int i = 0; i < s.size(); ++i) add(i), ++cnt[suff];
for (int i = nNode; i >= 0; --i)
cnt[Tree[i].link] += cnt[i];
long long ans = 0;
for (int i = 1; i <= nNode; ++i) ans = max(ans, cnt[i] * Tree[i].len);
cout << ans;
}
Compilation message (stderr)
# | 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... |