Cod sursa(job #2493861)

Utilizator SchnitzelMannPavaloiu Gabriel SchnitzelMann Data 17 noiembrie 2019 08:24:28
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.4 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in("pscpld.in");
ofstream out("pscpld.out");
string s;
long long a[2000002];
int main()
{
    long long n,i,j,c=1,p=2,S=1;
    in>>s;
	n=s.size()*2+1;
	a[1]=1;
	for(i=2;i<n;i++)
	{
		j=min(a[c*2-i],max(p-i,0LL));
		for(;i+j<n&&j<i&&((i+j)%2||s[(i+j+1)/2]==s[(i-j-1)/2]);j++);
		if(i+j>p)
			c=i,p=i+j;
		a[i]=j;
		S+=j/2+j%2;
	}
	out<<S;
    return 0;
}