제출 #1295858

#제출 시각아이디문제언어결과실행 시간메모리
1295858Jawad_Akbar_JJ회문 (APIO14_palindrome)C++20
100 / 100
626 ms80200 KiB
#include <iostream>
#include <map>

using namespace std;
#define int __int128
const int N = 3<<17;
int ph[N], sh[N], pw[N], mod = 100'000'000'000'000'037, 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] * 99991 + s[i-1]) % mod;
	for (int i=n;i>=1;i--)
		sh[i] = (sh[i+1] * 99991 + s[i-1]) % mod;
	for (int i=pw[0]=1;i<=n;i++)
		pw[i] = pw[i-1] * 99991 % 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<<(long long)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...