Submission #1296865

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

const int maxn = 100005,  baza = 29;
const long long MOD = 1e9+7;
int n;
string s;
int dn1[maxn], dp1[maxn], dn2[maxn], dp2[maxn];
int h[maxn], hr[maxn], mn[maxn];
long long smanji[maxn], povecaj[baza][maxn];
vector <int> dodajl[maxn], dodajr[maxn], maknil[maxn], maknir[maxn];
long long sumal, sumar, ukpl, ukpr, ans, poc;

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();
	
	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]));
		//cout << h[i] << endl;
	}
	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]));
		//cout << hr[i] << endl;
	}
	
	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];
		//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) == har(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) == har(i + dp1[i] + 2, i + dp1[i] + 1 + mid)) low = mid;
			else high = mid - 1;
		}
		dp2[i] = low;
		//cout << dp1[i] << " " << dp2[i] << endl;
	}
	poc += n;
	
	for (int i = 0; i < n; i++){
		dodajl[i - dn1[i]].push_back(i);
		maknil[i].push_back(i);
		dodajr[i + 1].push_back(i);
		maknir[i + 1 + dn1[i]].push_back(i);
	}
	for (int i = 0; i < n; i++){
		for (int j = 0; j < dodajl[i].size(); j++){
			int c = dodajl[i][j];
			sumal += dn1[c] - c + 1;
			ukpl++;
		}
		for (int j = 0; j < maknil[i].size(); j++){
			int c = maknil[i][j];
			sumal -= dn1[c] - c + 1;
			ukpl--;
		}
		for (int j = 0; j < dodajr[i].size(); j++){
			int c = dodajr[i][j];
			sumar += dn1[c] + c + 1;
			ukpr++;
		}
		for (int j = 0; j < maknir[i].size(); j++){
			int c = maknir[i][j];
			sumar -= dn1[c] + c + 1;
			ukpr--;
		}
		smanji[i] = sumal + sumar + ukpl * i - ukpr * i;
		povecaj[s[i] - 'a'][i] += sumal + sumar + ukpl * i - ukpr * i;
	}
	for (int i = 0; i < n; i++){
		dodajl[i].clear();
		maknil[i].clear();
		dodajr[i].clear();
		maknir[i].clear();
	}
	for (int i = 0; i < n - 1; i++){
		if (dp1[i] != 0){
			dodajl[i - dp1[i] + 1].push_back(i);
			maknil[i + 1].push_back(i);
			dodajr[i + 1].push_back(i);
			maknir[i + dp1[i] + 1].push_back(i);
		}
	}
	sumal = 0, sumar = 0, ukpl = 0, ukpr = 0;
	for (int i = 0; i < n; i++){
		for (int j = 0; j < dodajl[i].size(); j++){
			int c = dodajl[i][j];
			sumal += dp1[c] - c ;
			ukpl++;
		}
		for (int j = 0; j < maknil[i].size(); j++){
			int c = maknil[i][j];
			sumal -= dp1[c] - c;
			ukpl--;
		}
		for (int j = 0; j < dodajr[i].size(); j++){
			int c = dodajr[i][j];
			sumar += dp1[c] + c + 1;
			ukpr++;
		}
		for (int j = 0; j < maknir[i].size(); j++){
			int c = maknir[i][j];
			sumar -= dp1[c] + c + 1;
			ukpr--;
		}
		//cout << smanji[i] << " ";
		smanji[i] += sumal + sumar + ukpl * i - ukpr * i;
		povecaj[s[i] - 'a'][i] += sumal + sumar + ukpl * i - ukpr * i;
		//cout << smanji[i] << endl;
	}
	for (int slovo = 0; slovo < 26; slovo++){
		for (int i = 0; i < n; i++){
			
			if (i + dn1[i] < n - 1 and i - dn1[i] > 0 and s[i + dn1[i] + 1] - 'a' == slovo) povecaj[slovo][i - dn1[i] - 1] += dn2[i] + 1;
			if (i + dn1[i] < n - 1 and i - dn1[i] > 0 and s[i - dn1[i] - 1] - 'a' == slovo) povecaj[slovo][i + dn1[i] + 1] += dn2[i] + 1;
			
		}
		for (int i = 0; i < n - 1; i++){
			
			if (i + dp1[i] < n - 1 and i - dp1[i] + 1 > 0 and s[i + dp1[i] + 1] - 'a' == slovo) povecaj[slovo][i - dp1[i]] += dp2[i] + 1;
			if (i + dp1[i] < n - 1 and i - dp1[i] + 1 > 0 and s[i - dp1[i]] - 'a' == slovo) povecaj[slovo][i + dp1[i] + 1] += dp2[i] + 1;
			
		}
	}
	ans = poc;
	//cout << poc << endl;
	for (int i = 0; i < n; i++){
		long long maxi = 0;
		for (int slovo = 0; slovo < 26; slovo++) maxi = max(maxi, povecaj[slovo][i]);
		ans = max(ans, poc + maxi - smanji[i]);
		//cout << smanji[i] << " " << maxi << endl;
	}
	cout << ans << "\n";

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