# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
205626 | mihai50000 | Palindromes (APIO14_palindrome) | C++17 | 75 ms | 40976 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 int long long
struct PalTree
{
struct Node
{
map <char, int> urm;
int len;
int cnt;
int fail;
};
int n = 2;
int ans = 0;
vector <Node> vec;
PalTree(string s) : vec(s.size() + 2)
{
vec[0].fail = vec[0].len = -1;
vec[1].fail = vec[1].len = 0;
int last = 0;
for(int i = 0; i < s.size(); ++i)
{
char ch = s[i];
int pos = last;
while(s[i - vec[pos].len - 1] != ch)
{
pos = vec[pos].fail;
}
if(vec[pos].urm.count(ch))
{
pos = vec[pos].urm[ch];
vec[pos].cnt++;
last = pos;
continue;
}
vec[n].cnt = 1;
vec[n].len = vec[pos].len + 2;
vec[pos].urm[ch] = n;
int fail = vec[pos].fail;
while(fail != -1)
{
if(s[i - 1 - vec[fail].len] == ch && vec[fail].urm.count(ch))
{
fail = vec[fail].urm[ch];
break;
}
fail = vec[fail].fail;
}
if(fail < 1)
fail = 1;
vec[n].fail = fail;
last = n;
n++;
}
for(int i = n - 1; i > 0; --i)
{
vec[vec[i].fail].cnt += vec[i].cnt;
ans = max(ans, vec[i].cnt * vec[i].len);
}
}
};
main()
{
string s;
cin >> s;
PalTree arb(s);
cout << arb.ans << '\n';
}
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... |