Cod sursa(job #1584451)

Utilizator tudi98Cozma Tudor tudi98 Data 30 ianuarie 2016 09:41:47
Problema PScPld Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.68 kb
#include <fstream>
using namespace std;

string s;
int n;
int p[2][1000005];

void Manacher()
{
	int l = 0,r = -1;
	for (int t = 0; t < 2; t++)        // 0 = even length    1 = odd length
		for (int i = 0; i < n; i++)
		{
			p[t][i] = i > r ? (1-!t) : min(p[t][l+r-i+!t],r-i+1);
			int L = i - !t - p[t][i] + 1, R = i + p[t][i] - 1;
			while (L-1 >= 0 && R+1 < n && s[L-1] == s[R+1]) ++R,--L,++p[t][i];
			if (R > r)
				l = L,r = R;	
   		}
}


int main()
{
	ifstream fin("pscpld.in");
	ofstream fout("pscpld.out");

	fin >> s;
	n = s.size();
	Manacher();

	long long ret = 0;
	for (int i = 0; i < n; i++)
		ret += p[1][i] + p[0][i];

	fout << ret << "\n";
}