Cod sursa(job #1582518)

Utilizator tudi98Cozma Tudor tudi98 Data 27 ianuarie 2016 23:41:13
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 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 ? 1 : min(d1[l+r-i]+1,r-i+1);
		while (i+k <= n && i-k >= 1 && a[i+k] == a[i-k]) k++;
		d1[i] = k--;
		Ret += d1[i];
		if (i+k > r)
			l = i - k, r = i + k;
	}

	l = 1, r = 0;
	for (int i = 1; i <= n; i++)
	{
		int k = i > r ? 1 : min (d2[l+r-i+1]+1,r-i+1+1);
		while (i+k-i <= n && i-k >= 0 && 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("%ld",Manacher(strlen(a+1)));
}