Cod sursa(job #2232009)

Utilizator DenisacheDenis Ehorovici Denisache Data 16 august 2018 23:25:54
Problema PScPld Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <cstdio>
#include <cstring>

using namespace std;

int d1[1000005], d2[1000005];
char s[1000005];

int min(const int& a, const int& b) {
	return (a < b) ? a : b;
}

int main() {
	freopen("pscpld.in", "r", stdin);
	freopen("pscpld.out", "w", stdout);
	
	scanf("%s", s);
	int n = strlen(s);

	long long res = 0;
	int l = 0, r = -1;
	int k;

	for (int i = 0; i < n; ++i) {
		d1[i] = (i > r) ? 1 : min(d1[l + (r - i)], r - i);
		while (0 <= i - d1[i] && i + d1[i] < n && s[i - d1[i]] == s[i + d1[i]])
			d1[i]++;
		
		k = d1[i] - 1;
		if (i + k > r) {
			l = i - k;
			r = i + k;
		}
		
		d2[i] = (i > r) ? 0 : min(d2[l + (r - i) + 1], r - i + 1);
		while (0 <= i - d2[i] - 1 && i + d2[i] < n && s[i - d2[i] - 1] == s[i + d2[i]])
			d2[i]++;
		
		k = d2[i] - 1;
		if (i + k > r) {
			l = i - k - 1;
			r = i + k;
		}

		res += d1[i] + d2[i];
	}

	printf("%lld", res);

	return 0;
}