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;
struct nut
{
int len = 0, num = 0, suffLink = 0, child[26] = {0}, nlen = 0;
};
int curNode;
vector<nut> Tree;
string s;
void initPalinTree()
{
Tree.emplace_back();
Tree[0].len = 0, Tree[0].suffLink = 1;
Tree.emplace_back();
Tree[1].len = -1, Tree[1].suffLink = 1;
curNode = 0;
}
bool insert(int i)
{
int w = s[i] - 'a';
int x = curNode;
while (1)
{
int k = Tree[x].len;
if (i - k - 1 >= 0 && s[i - k - 1] == s[i])
break;
x = Tree[x].suffLink;
}
if (Tree[x].child[w])
return curNode = Tree[x].child[w], 0;
curNode = Tree.size();
Tree.emplace_back();
Tree[x].child[w] = curNode;
Tree[curNode].len = Tree[x].len + 2;
Tree[curNode].nlen = 1;
Tree[curNode].num = 1;
if (Tree[curNode].len == 1)
return Tree[curNode].suffLink = 0, 1;
while (1)
{
x = Tree[x].suffLink;
int k = Tree[x].len;
if (i - k - 1 >= 0 && s[i - k - 1] == s[i])
break;
}
Tree[curNode].suffLink = Tree[x].child[w];
Tree[curNode].num = Tree[Tree[curNode].suffLink].num + 1;
return 1;
}
void capnhatnguoc(int x)
{
while (x > 1) //Khi nao con khac hai nut goc
{
x = Tree[x].suffLink; //di nguoc len nut suffLink
if (x > 1)
Tree[x].nlen++;
}
}
int main()
{
//freopen("z.inp", "r", stdin);
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
initPalinTree();
cin >> s;
for (int i = 0; i < s.size(); i++)
{
insert(i);
capnhatnguoc(curNode);
}
long long ans = 1;
for (auto x : Tree)
ans = max(ans, 1ll * x.len * x.nlen);
cout << ans;
return 0;
}
Compilation message (stderr)
palindrome.cpp: In function 'int main()':
palindrome.cpp:69:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < s.size(); i++)
~~^~~~~~~~~~
# | 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... |