Submission #1218190

#TimeUsernameProblemLanguageResultExecution timeMemory
1218190Szymon_Pilipczuk회문 (APIO14_palindrome)C++20
100 / 100
97 ms45640 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; #define st first #define nd second #define pb push_back #define all(a) a.begin(),a.end() #define rep(a,b) for(int a = 0;a<b;a++) const int inf = 1e9; const ll infl = 1e18; vector<vector<int>> tr; int l(char c) { return int(c) - int('a'); } int main() { tr.resize(2); tr[0].resize(29); tr[1].resize(29); rep(i,26) { tr[0][i] = -1; tr[1][i] = -1; } tr[0][26] = 0; tr[0][27] = -1; tr[1][26] = 0; tr[1][27] = 0; tr[0][28] = 0; tr[1][28] = 0; int cu = 1; string s; cin>>s; rep(i,s.size()) { int c = l(s[i]); while(i-tr[cu][27]-1 < 0 || l(s[i-tr[cu][27]-1]) != c) { cu = tr[cu][26]; } /* if(i == 3) { return 0; }*/ if(tr[cu][c] == -1) { int cu2; if(cu != 0) { cu2 = tr[cu][26]; while(i-tr[cu2][27]-1 < 0 || l(s[i-tr[cu2][27]-1]) != c) { cu2 = tr[cu2][26]; } cu2 = tr[cu2][c]; } else { cu2 = 1; } // cout<<cu<<" "<<cu2<<endl; tr[cu][c] = tr.size(); vector<int> cc; rep(i,26) { cc.pb(-1); } cc.pb(cu2); cc.pb(tr[cu][27] + 2); cc.pb(1); tr.pb(cc); cu = tr[cu][c]; } else { cu = tr[cu][c]; tr[cu][28]++; } // cout<<i<<" "<<tr[cu][26]<<" "<<tr[cu][27]<<" "<<tr[cu][28]<<endl; } ll ans = 0; for(int i = tr.size()-1;i>=0;i--) { tr[tr[i][26]][28] += tr[i][28]; ans = max(ans,(ll) tr[i][28] * tr[i][27]); } cout<<ans; }
#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...