Cod sursa(job #2387481)

Utilizator shantih1Alex S Hill shantih1 Data 24 martie 2019 18:46:06
Problema PScPld Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.51 kb
#include <iostream>
#include <fstream>

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

int n,i,j,c,r,l,nr,dp[1000005];
char s[2000015];
string t;
long long rez;

int main() {
	
	getline(fin,t);
	
	n=1;
	s[1]='#';
	for(i=0;i<t.size();i++)
		s[++n]=t[i], s[++n]='#';
	
	c=1;
	r=1;
	for(i=2;i<=n;i++)
	{
		j=c-(i-c);
		if(r>i)
			dp[i]=min(r-i, dp[j]);
		
		while(s[i+dp[i]+1]==s[i-dp[i]-1])
			dp[i]++;
		
		if(i+dp[i]>r)
			c=i, r=dp[i];
		
		rez+=1LL*(dp[i]+1)/2;
	}
	
	fout<<rez<<"\n";
}