Cod sursa(job #2232019)

Utilizator DenisacheDenis Ehorovici Denisache Data 16 august 2018 23:47:34
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 kb
#include <cstdio>
#include <cstring>

using namespace std;

int d[2000005];
char s[2000005];

inline 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);
	
	int n = 0;
	s[n++] = '+';
	while (scanf("%c", &s[n++]) > 0)
		s[n++] = '+';

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

	for (int i = 1; i < n - 1; ++i) {
		d[i] = (i > r) ? 1 : min(d[l + (r - i)], r - i);

		while (0 <= i - d[i] && i + d[i] < n && s[i - d[i]] == s[i + d[i]]) {
			++d[i];
			r = i;
		}
		
		l = r - d[i] + 1;

		res += d[i] / 2;
	}

	printf("%lld", res);

	return 0;
}