Cod sursa(job #1967543)

Utilizator lflorin29Florin Laiu lflorin29 Data 16 aprilie 2017 19:37:35
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
const int MAX_N = 1e6 + 2;

char aux[MAX_N], s[2 * MAX_N];
int n, dp[MAX_N];

void Konstruieste()
{
	int m = 0;

	for (int i = 1; i <= n; ++i)
	{

		s[++m] = '#';
		s[++m] = aux[i];
	}

	s[++m] = '#';
	n = m;
}

void Manaker()
{
	long long ans = 0;
	int c = 0;

	for (int i = 2; i <= n; ++i)
	{
		dp[i] = 1;
		if(c + dp[c] > i) {
			dp[i] = min(c + dp[c] - i, dp[i - c]);
		}
		while (i - dp[i] > 0 && i + dp[i] <= n && s[i - dp[i]] == s[i + dp[i]])
			++dp[i];

		if (i % 2 == 0)
		{
			ans += (dp[i]) / 2;
		}
		else ans += (dp[i] - 1) / 2;
		if(i + dp[i] > c + dp[c])
			c = i;
	}

	fout << ans;

}
int main()
{
	fin >> (aux + 1);
	n = strlen(aux + 1);
	Konstruieste();
	Manaker();
}