Cod sursa(job #3236689)

Utilizator Dani111Gheorghe Daniel Dani111 Data 30 iunie 2024 13:35:28
Problema PScPld Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.58 kb
#include <bits/stdc++.h>
using namespace std;

const int MAX = 1000000;
const int MOD = 1e9 + 7;
string s;
long long H[MAX + 3];
long long H1[MAX + 3];
long long pww[MAX + 3];
int N;

long long pw(long long A, long long N) {
	if(N == 0) {
		return 1;
	}

	if(N % 2 == 1) { 
		return (1LL * A * pw(A, N - 1)) % MOD;
	}

	long long P = pw(A, N / 2) % MOD;

	return (1LL * P * P) % MOD;
}

bool hash2(int len, int i) {
	long long hash1 = 0, hash2 = 0;
	//if(i - 1 - len >= 0)
	hash1 = ((1LL * (H[i - 1] - H[i - 1 - len] + MOD) % MOD) * 1LL * pw(pww[i - len], MOD - 2)) % MOD;
	//else hash1 = ((1LL * (H[i - 1]) % MOD)) % MOD;
	hash2 = ((1LL * (H1[i] - H1[i + len] + MOD) % MOD) * 1LL * pw(pww[N - i - len], MOD - 2)) % MOD;

			//if(len == 1)
			//cout << hash1 << ' ' << hash2 << '\n';
	if(hash1 == hash2) return true;
	return false;
}

bool hash1(int len, int i) {
	long long hash1 = 0, hash2 = 0;
	//if(i - 1 - len >= 0)
	hash1 = ((1LL * (H[i - 1] - H[i - 1 - len] + MOD) % MOD) * 1LL * pw(pww[i - len], MOD - 2)) % MOD;
	//else hash1 = ((1LL * (H[i - 1]) % MOD)) % MOD;
	hash2 = ((1LL * (H1[i + 1] - H1[i + len + 1] + MOD) % MOD) * 1LL * pw(pww[N - i - len - 1], MOD - 2)) % MOD;

			//if(len == 1)
			//cout << hash1 << ' ' << hash2 << '\n';
	if(hash1 == hash2) return true;
	return false;
}

int main() {
	freopen("pscpld.in", "r", stdin);
	freopen("pscpld.out", "w", stdout);

	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(false);

	cin >> s;	

	N = s.size();

	pww[0] = 1;
	for(int i = 1; i <= N; i++) {
		pww[i] = (1LL * pww[i - 1] * 26) % MOD;
	}

	H[0] = (s[0] - 'a' + 1);
	for(int i = 0; i < N; i++) {
		H[i] = (H[i - 1] + 1LL * (s[i] - 'a' + 1) * pww[i]) % MOD;
	}

	H1[N - 1] = (s[N - 1] - 'a' + 1);
	int j = 1;
	for(int i = N - 2; i >= 0; i--) {
		H1[i] = (H1[i + 1] + 1LL * (s[i] - 'a' + 1) * pww[j]) % MOD;
		j++;
	}

	int cnt = N;
	// for(int i = 0; i < N; i++) {
	// 	cout << H1[i] << ' ';
	// }
	// cout << '\n';

		for(int i = 0; i < N; i++) {
			int st = 1, dr = min(i, N - i);

			int best = 0;
			while(st <= dr) {
				int mid = (st + dr) / 2;
				if(hash2(mid, i)) {
					st = mid + 1;
					best = mid;
				}
				else dr = mid - 1;
			}
			cnt += best;
			//cout << i << ' ' << best << ' ' << "par" << '\n';

			st = 1, dr = min(i, N - i - 1);
			best = 0;
			while(st <= dr) {
				int mid = (st + dr) / 2;
				if(hash1(mid, i)) {
					st = mid + 1;
					best = mid;
				}
				else dr = mid - 1;
			}
			cnt += best;

			//cout << i << ' ' << best << ' ' << "impar" << '\n';
		}

	cout << cnt;
}