Submission #205626

#TimeUsernameProblemLanguageResultExecution timeMemory
205626mihai50000Palindromes (APIO14_palindrome)C++17
100 / 100
75 ms40976 KiB
#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)

palindrome.cpp: In constructor 'PalTree::PalTree(std::__cxx11::string)':
palindrome.cpp:29:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < s.size(); ++i)
                  ~~^~~~~~~~~~
palindrome.cpp: At global scope:
palindrome.cpp:79:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
#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...