이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define FILL(i,n) memset(i,n,sizeof i)
#define X first
#define Y second
#define ET cout << "\n"
#define SZ(a) ((int)a.size())
#define ALL(v) v.begin(),v.end()
#define pb push_back
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#ifdef bbq
#define debug(...) {\
fprintf(stderr,"%s - %d (%s) = ",__PRETTY_FUNCTION__,__LINE__,#__VA_ARGS__);\
_do(__VA_ARGS__);\
}
#define DB(a,s,e) {for(int _i=s;_i<e;++_i) cerr << a[_i] << " ";cerr << "\n";}
template<typename T>void _do(T &&x){cerr<<x<<endl;}
template<typename T,typename ...S> void _do(T &&x,S &&...t){cerr<<x<<", ";_do(t...);}
template<typename a,typename b> ostream& operator << (ostream &s,const pair<a,b> &p){return s<<"("<<p.X<<","<<p.Y<<")";}
#else
#define debug(...)
#define DB(a,s,e)
#endif
struct palindromic_tree{
struct node{
int next[26],fail,len;
int cnt,num;//cnt: appear times, num: number of pal. suf.
node(int l=0):fail(0),len(l),cnt(0),num(0){
for(int i=0;i<26;++i)next[i]=0;
}
};
vector<node>St;
vector<char>s;
int last,n;
palindromic_tree():St(2),last(1),n(0){
St[0].fail=1, St[1].len=-1, s.pb(-1);
}
inline void clear(){
St.clear(), s.clear(), last=1, n=0;
St.pb(0), St.pb(-1);
St[0].fail=1, s.pb(-1);
}
inline int get_fail(int x){
while(s[n-St[x].len-1]!=s[n])x=St[x].fail;
return x;
}
inline void add(int c){
s.push_back(c-='a'), ++n;
int cur=get_fail(last);
if(!St[cur].next[c]){
int now=SZ(St);
St.pb(St[cur].len+2);
St[now].fail=St[get_fail(St[cur].fail)].next[c];
St[cur].next[c]=now;
St[now].num=St[St[now].fail].num+1;
}
last=St[cur].next[c], ++St[last].cnt;
}
inline void count(){// counting cnt
auto i=St.rbegin();
for(;i!=St.rend();++i){
St[i->fail].cnt+=i->cnt;
}
}
inline int size(){// The number of diff. pal.
return SZ(St)-2;
}
}pal;
string s;
int main()
{
IOS();
ll ans=0;
cin >> s;
for(char c:s)
pal.add(c);
pal.count();
for(int i=2;i<SZ(pal.St);++i)
ans=max(ans,(ll)pal.St[i].len*pal.St[i].cnt);
cout << ans << "\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |