Submission #251373

#TimeUsernameProblemLanguageResultExecution timeMemory
251373phuleethanhPalindromes (APIO14_palindrome)C++14
0 / 100
1091 ms5108 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...