Cod sursa(job #2289120)

Utilizator ButumAndreiButum Andrei ButumAndrei Data 24 noiembrie 2018 11:24:43
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.58 kb
#include <fstream>
#include <iostream>
#include <cstring>
using namespace std;
ifstream f("pscpld.in");
ofstream g("pscpld.out");
int n;
char s[1000005],a[2*1000005];
int P[2*1000005],R,c;
long long rez;
int main()
{
	f>>s;
	n=strlen(s);
	for(int i=0;i<n;i++)
	{
		a[2*i+1]=s[i];
		a[2*i]='*';
	}
	a[2*n]='*';
	for(int i=1;i<=2*n;i++)
	{
		if(i<=R)
			P[i]=min(P[2*c-i],R-i);
		for(;i+P[i]+1<=2*n&&i-P[i]-1>=0&&a[i+P[i]+1]==a[i-P[i]-1];P[i]++);
		if(i+P[i]>R)
			{R=i+P[i];
			c=i;
			}
		rez+=(P[i]+1)/2;
	}
	g<<rez;
	f.close();
	g.close();
	return 0;
}