Submission #592927

#	Time	Username	Problem	Language	Result	Execution time	Memory
592927		1ne	Palindromes (APIO14_palindrome)	C++14	23 / 100	1086 ms	15964 KiB

palindrome

#include<bits/stdc++.h>
using namespace std;
struct String_Hash{
	int p1 = 31;
	int p2 = 37;
	int n;
	const int mod1 = 1e9 + 7;
	const int mod2 = 1e9 + 9;
	vector<int>h1,h2;
	vector<int>pw1,pw2;
	void build(int N){
		n = N;
		h1.resize(n + 1,0);
		pw1.resize(n,0);
		h2.resize(n + 1,0);
		pw2.resize(n,0);
		pw1[0] = 1;
		pw2[0] = 1;
		for (int i = 0;i<n;++i){
			pw1[i] = (pw1[i - 1] * p1)%mod1;
			pw2[i] = (pw2[i - 1] * p2)%mod2;
		}
	}
	void compute_hash(string &s){
		for (int i = 0;i<n;++i){
			h1[i + 1] = (h1[i] + (s[i] - 'a' + 1) * pw1[i])%mod1;
			h2[i + 1] = (h2[i] + (s[i] - 'a' + 1) * pw2[i])%mod2;
		}
	}
	pair<int,int> gethash(int l,int r){
		//h[r] = h[l]*p[l - 1] + h[l + 1]* p[l].... h[r - 1] * p[r - 2]
		//h[l] = ...h[l - 1]*p[l - 2] + h[l]* p[l - 1]
		int cur_h1 = (h1[r] - h1[l] + mod1)%mod1;
		int cur_h2 = (h2[r] - h2[l] + mod2)%mod2;
		cur_h1 = (cur_h1 * pw1[n - l - 1])%mod1;
		cur_h2 = (cur_h2 * pw2[n - l - 1])%mod2;
		return make_pair(cur_h1,cur_h2);
	}
};
struct Manacher{
	string cur;
	vector<int>p;
	int n;
	void build(string s){
		n = (int)s.length();
		cur+='@';
		for (int i = 0;i<n;++i){
			cur+='#';
			cur+=s[i];
		}	
		cur+='#';
		cur+='$';
		n = 2 * n + 3;
		p.resize(n + 1);
		int l = 0,r = 0;
		for (int i = 1;i<n;++i){
			if (i < r){
				p[i] = min(r - i,p[l + (r - i)]);
			}
			while(cur[i - p[i] - 1] == cur[i + p[i] + 1])++p[i];
			if (r < i + p[i]){
				r = i + p[i];
				l = i - p[i];
			}
		}
	}
	string lpalin(){
		int sz = 0,ind = -1;
		for (int i = 0;i<=n;++i){
			int cursz = 0;
			if (cur[i] == '#'){
				cursz  = (p[i] + 1)/2 + (p[i] + 1)/2;
			}
			else{
				cursz = p[i]/2 + p[i]/2 + 1;
			}
			if (sz < cursz){
				sz = cursz;
				ind = i;
			}
		}
		string ans;
		for (int i = ind - p[ind];i<=ind + p[ind];++i){
			if (cur[i]!='#')ans+=cur[i];
		}
		return ans;
	}
};

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	string s;cin>>s;
	Manacher st;
	st.build(s);
	map<string,int>mp;
	String_Hash h;
	h.build((int)s.length());
	h.compute_hash(s);
	for (int i = 1;i<st.n;++i){
		if (st.p[i]){
			int l = (i - 1 - st.p[i])/2;
			int r = l + st.p[i] - 1;
			while(l<=r){
				//cout<<l<<" "<<r<<'\n';
				mp[s.substr(l,r - l + 1)]++;
				++l;
				--r;
			}
		}
	}
	int ans = 0;
	for (auto x:mp){
		ans = max(ans,(int)x.first.length() * x.second);
	}
	cout<<ans<<'\n';
	return 0;
}

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