Submission #251413

#TimeUsernameProblemLanguageResultExecution timeMemory
251413phuleethanhPalindromes (APIO14_palindrome)C++14
100 / 100
28 ms35464 KiB
#include <bits/stdc++.h> using namespace std; const int N = 303030; struct nut { int len = 0, occ = 0, suffLink = 0, child[26]; } Tree[N]; string s; int last, num; void insert(int i) { //Tim nut X to nhat thoa man while (i - Tree[last].len - 1 < 0 || s[i - Tree[last].len - 1] != s[i]) last = Tree[last].suffLink; int w = s[i] - 'a'; //Them moi : Neu nut nay chua co trong cay if (Tree[last].child[w] == 0) { //tim nut suffixLink tro toi int tmp = Tree[last].suffLink; while (i - Tree[tmp].len - 1 < 0 || s[i - Tree[tmp].len - 1] != s[i]) tmp = Tree[tmp].suffLink; //tao nut moi va tro vao day Tree[last].child[w] = ++num, Tree[num].len = Tree[last].len + 2; Tree[num].suffLink = (Tree[num].len == 1 ? 0 : Tree[tmp].child[w]); } last = Tree[last].child[w]; Tree[last].occ++; } int main() { //freopen("z.inp", "r", stdin); ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); Tree[1].len = -1, Tree[0].suffLink = Tree[1].suffLink = 1; last = 0, num = 1; cin >> s; for (int i = 0; i < s.size(); i++) insert(i); long long ans = 0; for (int i = num; i >= 2; i--) { ans = max(ans, 1ll * Tree[i].len * Tree[i].occ); Tree[Tree[i].suffLink].occ += Tree[i].occ; } cout << ans; return 0; }

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:39: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...