Cod sursa(job #2262547)

Utilizator cipri321Marin Ciprian cipri321 Data 17 octombrie 2018 16:34:18
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.57 kb
#include <fstream>
#include <iostream>
#include <cstring>
#define DIM 1000005
using namespace std;
ifstream fi("pscpld.in");
ofstream fo("pscpld.out");
int n;
char C[DIM],A[2*DIM];
int dp[2*DIM],st,dr,mid;
long long rez;
int main()
{
	fi>>C;
	n=strlen(C);
	for(int i=0;i<n;i++)
	{
		A[2*i+1]=C[i];
		A[2*i]='*';
	}
	A[2*n]='*';
	for(int i=1;i<=2*n;i++)
	{
		if(i<=dr)
			dp[i]=min(dp[2*mid-i],dr-i);
		for(;i+dp[i]+1<=2*n&&i-dp[i]-1>=0&&A[i+dp[i]+1]==A[i-dp[i]-1];dp[i]++);
		if(i+dp[i]>dr)
			dr=i+dp[i],mid=i;
		rez+=(dp[i]+1)/2;
	}
	fo<<rez;
	fi.close();
	fo.close();
	return 0;
}