제출 #738454

#제출 시각아이디문제언어결과실행 시간메모리
738454Abrar_Al_Samit회문 (APIO14_palindrome)C++17
0 / 100
1093 ms77704 KiB
#include<bits/stdc++.h>
using namespace std;

const int mod = 1e9 + 9;
const int b = 31;
const int nax = 10003;

map<long long,int>cnt;
string s;
long long p[nax];
int n;
long long pwr[nax];
long long ans = 0;

long long get(int l, int r) {
	long long ret = p[r];
	if(l) ret -= p[l-1];

	ret *= pwr[n-r-1];
	return ret;
}
void PlayGround() {
	cin>>s;
	n = s.size();

	long long pw = 1;
	for(int i=0; i<n; ++i) {
		pwr[i] = pw;
		p[i] = (pw * (s[i]-'a'+1));
		if(i) p[i] += p[i-1];

		p[i] %= mod;
		pw = (pw * b) % mod;
	}


	for(int i=0; i<n; ++i) {
		for(int j=0;  ; ++j) {
			if(i-j<0 || i+j>=n) break;
			if(s[i-j]!=s[i+j]) break;

			long long h_val = get(i-j, i+j);
			cnt[h_val]++;
			ans = max(ans, (j*2+1) * 1LL * cnt[h_val]);
		}
	}

	for(int i=0; i<n-1; ++i) {
		for(int j=0; ; ++j) {
			if(i-j<0 || i+j+1>=n) break;
			if(s[i-j]!=s[i+j+1]) break;

			long long h_val = get(i-j, i+j+1);
			cnt[h_val]++;
			ans = max(ans, (j+1)*2LL * cnt[h_val]);
		}
	}
	cout<<ans<<'\n';

	// cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	PlayGround();
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...