Cod sursa(job #2232037)

Utilizator DenisacheDenis Ehorovici Denisache Data 17 august 2018 01:38:41
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <fstream>
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;


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

int main() {
	ios::sync_with_stdio(false);

	ifstream cin("pscpld.in");
	ofstream cout("pscpld.out");

	cin >> s;
	int n = strlen(s);
	int k;
	long long res = 0;

	for (int i = 0, l = 0, r = -1; 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;
		}
	}

	for (int i = 0, l = 0, r = -1; i < n; ++i) {
		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];
	}

	cout << res;

	return 0;
}