Cod sursa(job #2723111)

Utilizator FrostfireMagirescu Tudor Frostfire Data 13 martie 2021 16:00:13
Problema PScPld Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.73 kb
#include <iostream>
#include <fstream>
#include <cstring>
#define ll long long
#define NMAX 1000000

using namespace std;

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

char s[NMAX+10], t[2*NMAX+10];
ll ans;
int k, v[NMAX+10];

int main()
{
	fin >> s;
	t[++k] = '&';
	t[++k] = '#';
	int n = strlen(s);
	for(int i=0; i<n; i++)
		{	t[++k] = s[i];
			t[++k] = '#';
		}
	t[++k] = '%';
	int C = 0, R = 0;
	for(int i=1; i<k; i++)
		{	int ogl = 2 * C - i;
			if(i < R) v[i] = min(R - i, v[ogl]);
			while(t[i+v[i]+1] == t[i-v[i]-1])
				v[i]++;
			if(i + v[i] > R)
				{	C = i;
					R = i + v[i];
				}	
		}
	for(int i=0; i<k; i++)
		ans = ans + ((ll)v[i] + 1) / 2;
	fout << ans << '\n';
	return 0;
}