Submission #262363

#	Time	Username	Problem	Language	Result	Execution time	Memory
262363		baluteshih	Palindromes (APIO14_palindrome)	C++14	100 / 100	82 ms	63440 KiB

palindrome

#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";
}

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 26 / 26
• Subtask 5: 27 / 27