Submission #1211304

#TimeUsernameProblemLanguageResultExecution timeMemory
1211304k1r1t0회문 (APIO14_palindrome)C++20
100 / 100
50 ms71120 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int N = 310000; const int K = 26; int s[N], len[N], lnk[N], to[N][K], cnt[N], n, suff, last; void init() { s[n++] = -1; lnk[0] = 1; len[1] = -1; last = 1; } int get_link(int v) { while (s[n - len[v] - 2] != s[n - 1]) v = lnk[v]; return v; } void add_char(int c) { s[n++] = c; suff = get_link(suff); if (!to[suff][c]) { last++; len[last] = len[suff] + 2; lnk[last] = to[get_link(lnk[suff])][c]; to[suff][c] = last; } suff = to[suff][c]; cnt[suff]++; } void count() { for (int i = last; i >= 0; i--) cnt[lnk[i]] += cnt[i]; } int solve() { int ans = 0; for (int i = 0; i <= last; i++) ans = max(ans, len[i] * cnt[i]); return ans; } int32_t main() { ios::sync_with_stdio(0); cin.tie(0); init(); string s; cin >> s; for (char c : s) add_char(c - 'a'); count(); cout << solve(); }
#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...