# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
47991 | Kmcode | Palindromes (APIO14_palindrome) | C++14 | 26 ms | 31648 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"
using namespace std;
#define MAX 300015
char buf[MAX];
string s;
int len[MAX];
int linkk[MAX];
int nex[MAX][26];
int ord;
int cur;
int cnt[MAX];
void append(int idx) {
char c = s[idx];
while (!(idx-len[cur]-1>=0&&s[idx]==s[idx-len[cur]-1])) {
cur = linkk[cur];
}
if (nex[cur][c - 'a'] == -1) {
nex[cur][c - 'a'] = ord;
ord++;
len[nex[cur][c - 'a']] = len[cur] + 2;
linkk[nex[cur][c - 'a']] = linkk[cur];
cur = nex[cur][c - 'a'];
if (len[cur] == 1) {
linkk[cur] = 1;
}
else {
while (nex[linkk[cur]][c - 'a'] == -1) {
linkk[cur] = linkk[linkk[cur]];
}
if (linkk[cur] <= 0)exit(1);
linkk[cur] = nex[linkk[cur]][c - 'a'];
}
}
else {
cur = nex[cur][c - 'a'];
}
cnt[cur]++;
}
int main() {
memset(nex, -1,sizeof(nex) );
len[0] = -1;
len[1] = 0;
ord = 2;
scanf("%s", buf);
s = buf;
linkk[1] = 0;
linkk[0] = -1;
for (int i = 0; i < s.size(); i++) {
append(i);
}
long long int ans = 0;
for (int i = ord - 1; i >= 2; i--) {
cnt[linkk[i]] += cnt[i];
ans = max(ans, (long long int)(len[i])*cnt[i]);
}
printf("%lld\n", ans);
return 0;
}
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... |