Cod sursa(job #2701401)

Utilizator hurjui12AlexandruHurjui Alexandru-Mihai hurjui12Alexandru Data 30 ianuarie 2021 19:59:54
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.7 kb
#include <fstream>
#include <cstring>
using namespace std;

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

char buff[1000001], c[2000005];
int pal[2000005];

int main()
{
	int nbuff, n, i, st, dr, k;
	fin >> buff;
	nbuff = strlen(buff);
	c[0] = '#';
	for (i = 0; i<nbuff; i++)
	{
		c[2*i+1] = buff[i];
		c[2*i+2] = '#';
	}
	
	n = nbuff*2 + 3;
	st = dr = -1;
	for (i = 0; i<n; i++)
	{
		if (i <= dr)
			k = min(pal[st + dr - i], dr - i + 1);
		else
			k = 1;
		
		while (0 <= i-k && i+k < n && c[i-k] == c[i+k])
			k++;
		
		pal[i] = k;
		k--;
		if (i + k > dr)
		{
			dr = i + k;
			st = i - k;
		}
	}
	
	long long rasp = 0;
	for (i = 0; i<n; i++)
		rasp = rasp + pal[i]/2;
	fout << rasp;
	return 0;
}