Cod sursa(job #2723146)

Utilizator hurjui12AlexandruHurjui Alexandru-Mihai hurjui12Alexandru Data 13 martie 2021 16:50:03
Problema PScPld Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.68 kb
#include <fstream>
#include <string>
using namespace std;

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

string buff, s;
int pal[2000005];

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