Cod sursa(job #2135909)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 19 februarie 2018 14:47:27
Problema PScPld Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.72 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fi("pscpld.in");
ofstream fo("pscpld.out");

using i64 = long long;

const int N = 1e6 + 5;

int pal[N];
char tmp[N], str[2 * N];

i64 ant;
int n, p;

int main() {
	fi >> (tmp + 1);

	n = strlen(tmp + 1);
	for (int i = 1; i <= n; ++i) {
		str[2 * i - 1] = tmp[i];
		str[2 * i] = '*'; }

	n = 2 * n - 1;
	str[n + 1] = '\0';
	str[0] = '@';

	p = 1;
	for (int i = 1; i <= n; ++i) {
		pal[i] = max(1, min(p + pal[i] - i, pal[p - (i - p)]));

		while (str[i - pal[i]] == str[i + pal[i]])
			++pal[i];

		if (i + pal[i] >= p + pal[p])
			p = i; }

	for (int i = 1; i <= n; ++i)
		if (str[i] == '*')
			ant+= pal[i] / 2;
		else
			ant+= (pal[i] + 1) / 2;

	fo << ant << endl;

	return 0; }