Submission #111219

#	Time	Username	Problem	Language	Result	Execution time	Memory
111219		user202729	Palindromes (APIO14_palindrome)	C++17	100 / 100	100 ms	61076 KiB

palindrome

#include<iostream>
#include<array>
#include<cassert>
#include<vector>

struct PalinTree{
	static int constexpr MIN='a',CNT=26;
	using Idx=int;

	static Idx constexpr NONE=-1;

	struct Node{
		std::array<Idx,CNT> c; // children
		Idx link; // suffix link
		int len;

		// will be used to store number of occurences in the string
		int cnt;

		Node():link(0x12345678),len(0x12345678),cnt(0){
			for(Idx& i:c)i=NONE;
		}
	};

	std::vector<Node> d;
	static Idx constexpr ZERO=0, // node coer to emt string
			   NEG=1; // node coer to the "len = -1" string

	template<class Fn>
	Idx newnode(Fn f){
		auto n=(Idx)d.size();
		d.push_back({});
		f(d.back());
		return n;
	}

	template<class Fn>
	Idx child(Idx a,char c,
			Fn f // used in case a new node is constructed
			// void(Node&)
			){
		c-=MIN;
		if(d[a].c[c]<0){
			Idx ans=newnode(f);
			d[a].c[c]=ans;
			return ans;
		}
		return d[a].c[c];
	}

	// std::string s;
	PalinTree(std::string const s):
		d(2)
		// ,s(std::move(_s))
	{
		d[ZERO].link=NEG;
		d[ZERO].len=0;
		d[NEG].len=-1;

		Idx n=ZERO; // current node
		for(unsigned i=0;i<s.size();++i){
			char c=s[i];
			while(true){
				int j=i-d[n].len;
				if(j!=0&&s[j-1]==c){
					int newlen=d[n].len+2;
					Idx oldlink=d[n].link;
					n=child(n,c,[&](Node& z){
							z.len=newlen;
							if(newlen==1)
								z.link=ZERO;
							else{
								Idx l=oldlink;
								while(c!=s[i-d[l].len-1])
									l=d[l].link;
								z.link=d[l].c[c-MIN];
								assert(z.link!=NONE);
							}
							});
					break;
				}
				n=d[n].link;
			}
			++d[n].cnt;
		}

		// accumulate cnt by link edge
		std::vector<Idx> ns; // list of nodes sorted by order
		ns.reserve(d.size());
		ns.push_back((Idx)NEG);
		ns.push_back((Idx)ZERO);
		for(unsigned i=0;i<d.size();++i){
			for(Idx c:d[ns[i]].c)
				if(c>=0)
					ns.push_back(c);
		}
		assert(ns.size()==d.size());

		for(unsigned i=d.size()-1;i;--i){
			int n=ns[i];
			d[d[n].link].cnt+=d[n].cnt;
		}
	}
};

int main(){
	std::ios::sync_with_stdio(0);std::cin.tie(0);
	std::string s;std::cin>>s;
	PalinTree t(s);
	int64_t ans=0;
	for(unsigned i=2;i<t.d.size();++i)
		ans=std::max(ans,(int64_t)t.d[i].len*t.d[i].cnt);
	std::cout<<ans<<'\n';
}

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