Cod sursa(job #3236684)

Utilizator Dani111Gheorghe Daniel Dani111 Data 30 iunie 2024 13:07:09
Problema PScPld Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.86 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];

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;
}

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

	cin >> s;	

	int 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 len = 1; len <= N / 2; len++) {
		//aa 
		for(int i = len; i <= N - len; i++) {
			long long hash1 = 0, hash2 = 0;
			hash1 = ((1LL * (H[i - 1] - H[i - 1 - len] + MOD) % MOD) * 1LL * pw(pw(26, i - len), MOD - 2)) % MOD;
			hash2 = ((1LL * (H1[i] - H1[i + len] + MOD) % MOD) * 1LL * pw(pw(26, (N - i - len)), MOD - 2)) % MOD;

			//if(len == 1)
			//cout << hash1 << ' ' << hash2 << '\n';
			if(hash1 == hash2) cnt++;
		}
		//cout << '\n';
		for(int i = len; i <= N - len - 1; i++) {
			long long hash1 = 0, hash2 = 0;
			hash1 = ((1LL * (H[i - 1] - H[i - 1 - len] + MOD) % MOD) * 1LL * pw(pw(26, i - len), MOD - 2)) % MOD;
			hash2 = ((1LL * (H1[i + 1] - H1[i + len + 1] + MOD) % MOD) * 1LL * pw(pw(26, (N - i - len - 1)), MOD - 2)) % MOD;

			//if(len == 1)
			//cout << hash1 << ' ' << hash2 << '\n';
			if(hash1 == hash2) cnt++;
		}

	}
	cout << cnt;
}