Cod sursa(job #2739071)

Utilizator hurjui12AlexandruHurjui Alexandru-Mihai hurjui12Alexandru Data 6 aprilie 2021 19:24:32
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.66 kb
#include <fstream>
#include <string>
using namespace std;

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

string buff, a;
int pal[2000005];

int main()
{
	int n, i, l, st, dr;
	long long rasp = 0;
	fin >> buff;
	a.push_back('#');
	for (i = 0; i<buff.size(); i++)
	{
		a.push_back(buff[i]);
		a.push_back('#');
	}
	n = a.size();
	st = dr = -1;
	for (i = 0; i<n; i++)
	{
		if (i <= dr)
			l = min(pal[st + dr - i], dr - i + 1);
		else
			l = 1;
		
		while (0 <= i-l && i + l < n && a[i-l] == a[i+l])
			l++;
		
		pal[i] = l;
		l--;
		if (i + l > dr)
		{
			dr = i + l;
			st = i - l;
		}
	}
	for (i = 0; i<n; i++)
		rasp = rasp + pal[i]/2;
	fout << rasp;
	return 0;
}