Submission #1255918

#TimeUsernameProblemLanguageResultExecution timeMemory
1255918abc864197532회문 (APIO14_palindrome)C++17
100 / 100
21 ms35140 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; #define pb push_back #define all(a) a.begin(), a.end() #define sz(a) ((int)a.size()) #ifdef Doludu template <typename T> ostream& operator << (ostream &o, vector <T> vec) { o << "{"; int f = 0; for (T i : vec) o << (f++ ? " " : "") << i; return o << "}"; } void bug__(int c, auto ...a) { cerr << "\e[1;" << c << "m"; (..., (cerr << a << " ")); cerr << "\e[0m" << endl; } #define bug_(c, x...) bug__(c, __LINE__, "[" + string(#x) + "]", x) #define bug(x...) bug_(32, x) #define bugv(x...) bug_(36, vector(x)) #define safe bug_(33, "safe") #else #define bug(x...) void(0) #define bugv(x...) void(0) #define safe void(0) #endif const int mod = 998244353, N = 500007, logN = 18, C = 26; struct PAM { int ch[N][C], cnt[N], fail[N], len[N], _id; // 0 -> even root, 1 -> odd root PAM () { reset(); } int newnode() { fill_n(ch[_id], C, 0); cnt[_id] = fail[_id] = len[_id] = 0; return _id++; } void build(string s) { int lst = 1; for (int i = 0; i < sz(s); ++i) { while (s[i - len[lst] - 1] != s[i]) lst = fail[lst]; if (!ch[lst][s[i] - 'a']) { int idx = newnode(); len[idx] = len[lst] + 2; int now = fail[lst]; while (s[i - len[now] - 1] != s[i]) now = fail[now]; fail[idx] = ch[now][s[i] - 'a']; ch[lst][s[i] - 'a'] = idx; } lst = ch[lst][s[i] - 'a'], cnt[lst]++; } } void build_count() { for (int i = _id - 1; i > 1; --i) cnt[fail[i]] += cnt[i]; } void reset() { _id = 0, newnode(), newnode(), len[0] = 0, fail[0] = 1, len[1] = -1; } } pam; int main() { ios::sync_with_stdio(false), cin.tie(0); string s; cin >> s; pam.build(s); pam.build_count(); ll ans = 0; for (int i = 2; i < pam._id; ++i) { ans = max(ans, 1ll * pam.len[i] * pam.cnt[i]); } cout << ans << "\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...