Submission #30166

#TimeUsernameProblemLanguageResultExecution timeMemory
30166Andrei1998Palindromes (APIO14_palindrome)C++14
100 / 100
129 ms92588 KiB
#include <bits/stdc++.h> using namespace std; const int NMAX = 2 * 300000 + 5; inline int toInt(char ch) { if (ch == '#') return 0; else return ch - 'a' + 1; } string str; int nodes; int alf[NMAX][27]; int h[NMAX]; int father[NMAX]; int ext[NMAX]; int whichNode[NMAX]; int cnt[NMAX]; long long int ans = 1; void dfs(int node, int realH) { for (int i = 0; i < 27; ++ i) if (alf[node][i]) { dfs(alf[node][i], realH + (i > 0) * (1 + (node > 1))); cnt[node] += cnt[alf[node][i]]; } ans = max(ans, 1LL * realH * cnt[node]); } int main() { //freopen("data.in", "r", stdin); cin >> str; string str2 = "#"; for (auto it: str) { str2 += it; str2 += '#'; } str = str2; str = " " + str; int N = str.size() - 1; ++ nodes; int center = 0; for (int i = 1; i <= N; ++ i) { int node = 1; int l = 0; if (center + ext[center] - 1 >= i) { node = whichNode[2 * center - i]; l = h[node]; while (l > center + ext[center] - i) { node = father[node]; l --; } } while (i - l >= 1 && i + l <= N && str[i - l] == str[i + l]) { if (!alf[node][toInt(str[i - l])]) { alf[node][toInt(str[i - l])] = ++ nodes; h[nodes] = 1 + h[node]; father[nodes] = node; } node = alf[node][toInt(str[i - l])]; ++ l; } ext[i] = l; whichNode[i] = node; ++ cnt[node]; if (i + ext[i] > center + ext[center]) center = i; } dfs(1, 0); cout << ans << '\n'; return 0; }
#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...