제출 #67436

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
67436		KLPP	Palindromes (APIO14_palindrome)	C++14	23 / 100	1087 ms	8896 KiB

palindrome

#include<iostream>
#include<map>
using namespace std;
typedef long long int lld;
#define MOD 1000000007
#define BASE 257
lld hash2[1000000];
lld hash3[1000000];
lld pow[1000000];
int n;
bool palindrome(int a, int b){
	lld A=hash3[b+1]-hash3[a];
	A*=pow[n-1-a];
	lld B=hash2[a]-hash2[b+1];
	B*=pow[b];
	A%=MOD;
	B%=MOD;
	if(B<0)B+=MOD;
	if(A<0)A+=MOD;
	//cout<<a<<" "<<b<<" "<<A<<" "<<B<<endl;
	if(A%MOD==B%MOD)return true;
	return false; 
}
lld val(int a, int b){
	lld A=hash3[b+1]-hash3[a];
	A*=pow[n-1-a];
	A%=MOD;
	if(A<0)A+=MOD;
	return A; 
}
int main(){
	string s;
	cin>>s;
	n=s.size();
	hash3[0]=0;
	lld v=1;
	for(int i=1;i<=n;i++){
		hash3[i]=(s.at(i-1))*v+hash3[i-1];
		hash3[i]%=MOD;
		pow[i-1]=v;
		v*=BASE;
		v%=MOD;
	}
	hash2[n]=0;
	v=1;
	for(int i=n-1;i>-1;i--){
		hash2[i]=(s.at(i))*v+hash2[i+1];
		hash2[i]%=MOD;
		v*=BASE;
		v%=MOD;
	}
	//cout<<hash2[0]<<" "<<hash[n]<<endl;
	lld ans=0;
	for(lld len=1;len<=n;len++){
		map<lld,int> m;
		//cout<<hash[i]<<" "<<hash2[i]<<endl;
		for(int i=0;i+len-1<n;i++){
			if(palindrome(i,i+len-1)){
				lld H=val(i,i+len-1);
				map<lld,int>::iterator it=m.find(H);
				if(it==m.end()){
					m[H]=1;
					ans=max(ans,len);
					//cout<<len<<endl;
				}else{
					it->second++;
					ans=max(ans,it->second*len);
					//cout<<it->second*len<<endl;
				}
			}
		}
		//cout<<(hash[i]+hash2[i])%MOD<<endl;
	}cout<<ans<<endl;
	//cout<<palindrome(0,2)<<endl;
	
}

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