Submission #205608

#TimeUsernameProblemLanguageResultExecution timeMemory
205608mihai50000Palindromes (APIO14_palindrome)C++17
0 / 100
48 ms30228 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) { int m = s.size(); vec[0].len = vec[0].fail = -1; vec[1].len = vec[1].fail = 0; int last = 0; for(int i = 0; i < m; ++i) { char ch = s[i]; while(s[i - 1 - vec[last].len] != ch) last = vec[last].fail; if(vec[last].urm.count(ch)) { last = vec[last].urm[ch]; vec[last].cnt++; continue; } vec[n++].len = vec[last].len + 2; vec[n - 1].cnt = 1; vec[last].urm[ch] = n - 1; int fail = vec[last].fail; last = n - 1; while(fail != -1 && ch != s[i - 1 - vec[fail].len]) { fail = vec[fail].fail; } if(fail < 1) fail = 1; vec[last].fail = fail; } for(int i = n - 1; i > 0; --i) vec[vec[i].fail].cnt += vec[i].cnt; for(int i = 1; i < n; ++i) { ans = max(ans, vec[i].len * vec[i].cnt); } } }; main() { string s; cin >> s; PalTree arb(s); cout << arb.ans << '\n'; }

Compilation message (stderr)

palindrome.cpp:76: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...