Cod sursa(job #1584353)

Utilizator tudi98Cozma Tudor tudi98 Data 29 ianuarie 2016 22:54:28
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <bits/stdc++.h>
using namespace std;

char a[1000001];
int d1[1000001];
int d2[1000001];

long long Manacher(int n)
{
	long long Ret = 0;
	int l = 1,r = 0;

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

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

int main()
{
	freopen("pscpld.in", "r", stdin);
	freopen("pscpld.out", "w", stdout);

	gets(a+1);
	printf("%lld",Manacher((int)strlen(a+1)));
}