Submission #1296858

#TimeUsernameProblemLanguageResultExecution timeMemory
1296858mdobricPalinilap (COI16_palinilap)C++20
0 / 100
1095 ms3336 KiB
#include <bits/stdc++.h>
using namespace std;

const int maxn = 100005,  baza = 29;
const long long MOD = 998244353;
int n;
string s, s2;
int dn1[maxn], dp1[maxn], dn2[maxn], dp2[maxn];
int h[maxn], hr[maxn], mn[maxn];
long long poc, ans;
string znak = "abcdefghijklmnopqrstuvwxyz";

int add (int x, int y){
	if (x + y >= MOD) return x + y - MOD;
	if (x + y < 0) return x + y + MOD;
	return x + y;
}

long long umn (long long x, long long y){
	return (x * y) % MOD;
}

int ha (int x, int y){
	if (x == 0) return umn(h[y], mn[n - 1 - y]);
	else return umn(h[y] - h[x - 1], mn[n - 1 - y]);
}

int har (int x, int y){
	if (y == n - 1) return umn(hr[x], mn[x]);
	else return umn(hr[x] - hr[y + 1], mn[x]);
}

int main (void){
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> s;
	n = s.size();
	s2 = s;
	for (int slovo = 0; slovo < 26; slovo++){
		for (int pos = 0; pos < n; pos++){
			s[pos] = znak[slovo];
			poc = 0;
			h[0] = s[0] - 'a' + 1;
			mn[0] = 1;
			for (int i = 1; i < n; i++){
				mn[i] = umn(mn[i - 1], baza);
				h[i] = add(h[i - 1], umn((s[i] - 'a' + 1), mn[i]));
			}
			hr[n - 1] = s[n - 1] - 'a' + 1;
			for (int i = n - 2; i >= 0; i--){
				hr[i] = add(hr[i + 1], umn((s[i] - 'a' + 1), mn[n - i - 1]));
			}
			for (int i = 0; i < n; i++){
				int low = 0, high = min(i, n - 1 - i), mid;
				while (low < high){
					mid = (low + high) / 2 + 1;
					if (ha(i - mid, i - 1) == har(i + 1, i + mid)) low = mid;
					else high = mid - 1;
				}
				dn1[i] = low;
				low = 0, high = min(i - dn1[i] - 1, n - 2 - (dn1[i] + i));
				while (low < high){
					mid = (low + high) / 2 + 1;
					if (ha(i - dn1[i] - 1 - mid, i - dn1[i] - 2) == har(i + dn1[i] + 2, i + dn1[i] + 1 + mid)) low = mid;
					else high = mid - 1;
				}
				dn2[i] = low;
				poc += dn1[i];
				
				//if (pos == 1 and slovo == 2) cout << dn1[i] << " " << dn2[i] << endl;
			}
			
			for (int i = 0; i < n - 1; i++){
				int low = 0, high = min(i + 1, n - 1 - i), mid;
				while (low < high){
					mid = (low + high) / 2 + 1;
					if (ha(i - mid + 1, i) == ha(i + 1, i + mid)) low = mid;
					else high = mid - 1;
				}
				dp1[i] = low;
				poc += dp1[i];
				low = 0, high = min(i - dp1[i], n - 2 - (dp1[i] + i));
				while (low < high){
					mid = (low + high) / 2 + 1;
					if (ha(i - dp1[i] - mid, i - dp1[i] - 1) == ha(i + dp1[i] + 2, i + dp1[i] + 1 + mid)) low = mid;
					else high = mid - 1;
				}
				dp2[i] = low;
				
				//if (pos == 1 and slovo == 2) cout << dp1[i] << " " << dp2[i] << endl;
			}
			poc += n;
			s = s2;
			ans = max(ans, poc);
		}
	}
	cout << ans << "\n";

	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...