Submission #555972

#TimeUsernameProblemLanguageResultExecution timeMemory
555972hollwo_pelwPalindromes (APIO14_palindrome)C++17
100 / 100
24 ms34948 KiB
#include <bits/stdc++.h> // #include <ext/pb_ds/assoc_container.hpp> // #include <ext/pb_ds/trie_policy.hpp> // #include <ext/rope> using namespace std; // using namespace __gnu_cxx; // using namespace __gnu_pbds; void Hollwo_Pelw(); signed main(){ #ifndef hollwo_pelw_local if (fopen("hollwo_pelw.inp", "r")) assert(freopen("hollwo_pelw.inp", "r", stdin)), assert(freopen("hollwo_pelw.out", "w", stdout)); #else using namespace chrono; auto start = steady_clock::now(); #endif cin.tie(0), cout.tie(0) -> sync_with_stdio(0); int testcases = 1; // cin >> testcases; for (int test = 1; test <= testcases; test++){ // cout << "Case #" << test << ": "; Hollwo_Pelw(); } #ifdef hollwo_pelw_local auto end = steady_clock::now(); cout << "\nExecution time : " << duration_cast<milliseconds> (end - start).count() << "[ms]" << endl; #endif } const int N = 3e5 + 5; int n, siz[N], cnt[N], slink[N], tr[N][26], nnode = 1; char s[N]; void Hollwo_Pelw(){ cin >> (s + 1), n = strlen(s + 1); siz[0] = -1; for (int i = 1, c = 1; i <= n; i++) { while (s[i] != s[i - siz[c] - 1]) c = slink[c]; if (!tr[c][s[i] - 'a']) { int p = slink[c]; while (s[i] != s[i - siz[p] - 1]) p = slink[p]; p = max(1, tr[p][s[i] - 'a']); tr[c][s[i] - 'a'] = ++ nnode; slink[nnode] = p, siz[nnode] = siz[c] + 2; } cnt[c = tr[c][s[i] - 'a']] ++; } long long res = 0; for (int i = nnode; i; i--) { cnt[slink[i]] += cnt[i]; res = max(res, 1ll * cnt[i] * siz[i]); } cout << res << '\n'; }
#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...