Submission #1295744

#TimeUsernameProblemLanguageResultExecution timeMemory
1295744Jawad_Akbar_JJPalindromes (APIO14_palindrome)C++20
47 / 100
285 ms42224 KiB
#include <iostream>
#include <map>

using namespace std;
#define int long long
const int N = 3<<17;
int ph[N], sh[N], pw[N], mod = 999999937, Ans;
map<int, int> cnt[N], prv;

int get1(int l, int r){
	return (ph[r] - ph[--l] * pw[r - l] % mod + mod) % mod;
}

int get2(int l, int r){
	return (sh[l] - sh[++r] * pw[r - l] % mod + mod) % mod;
}

signed main(){
	string s;
	cin>>s;
	int n = s.size();

	for (int i=1;i<=n;i++)
		ph[i] = (ph[i-1] * 256 + s[i-1]) % mod;
	for (int i=n;i>=1;i--)
		sh[i] = (sh[i+1] * 256 + s[i-1]) % mod;
	for (int i=pw[0]=1;i<=n;i++)
		pw[i] = pw[i-1] * 256 % mod;

	for (int i=1;i<=n;i++){
		int l = 0, r = min(i, n - i + 1) + 1, h, hh;

		while (l + 1 < r){
			int mid = (l + r) / 2;
			if (get1(i - mid + 1, i) == get2(i, i + mid - 1))
				l = mid;
			else
				r = mid;
		}

		///////////////////////////////////////////////////
		h = get1(i - l + 1, i);
		cnt[l + l - 1][h]++;
		
		while (l >= 1 and prv.find(h) == prv.end()){
			l--;
			hh = get1(i - l + 1, i);
			prv[h] = hh, h = hh;
		}
		//////////////////////////////////////////////////


		l = 0, r = min(i - 1, n - i + 1) + 1;
		while (l + 1 < r){
			int mid = (l + r) / 2;
			if (get1(i - mid, i-1) == get2(i, i + mid - 1))
				l = mid;
			else
				r = mid;
		}

		//////////////////////////////////////////////////
		h = get1(i - l, i - 1);
		cnt[l + l][h]++;

		while (l >= 1 and prv.find(h) == prv.end()){
			l--;
			hh = get1(i - l, i - 1);
			prv[h] = hh, h = hh;
		}
	}

	for (int i=n;i>=1;i--){
		for (auto [j, k] : cnt[i]){
			Ans = max(Ans, i * k);
			if (i - 2 > 0)
				cnt[i - 2][prv[j]] += k;
		}
	}

	cout<<Ans<<'\n';
}
#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...