Cod sursa(job #2387512)

Utilizator shantih1Alex S Hill shantih1 Data 24 martie 2019 19:52:19
Problema PScPld Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <fstream>
#include <cstring>

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

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

int main() {
	
	fin >> (t + 1);
 
	n =(int) strlen(t + 1);
	rez=n;
	for (int i = 1; i <= n; ++i) {
		s[2 * i - 1] = t[i];
		s[2 * i] = '#'; }
 
	n = 2 * n - 1;
	s[n + 1] = '*';
	s[0] = '$';
	
	c=1;
	r=1;
	for(int i=2;i<=n;++i)
	{
		if(r>i)
			dp[i]=min(r-i, dp[2*c-i]);
		
		while(s[i+dp[i]]==s[i-dp[i]])
			dp[i]++;
		dp[i]--;
		
		if(i+dp[i]>r)	c=i, r=dp[i];
		
		rez+=1LL*dp[i]/2;
	}
	
	/*
	rez=l;
	c=1;
	r=1;
	for(i=2;i<=n;i++)
	{
		if(r>i)
			dp[i]=min(r-i, dp[2*c-i]);
		
		while(s[i+dp[i]]==s[i-dp[i]])
			dp[i]++;
		dp[i]--;
		
		if(i+dp[i]>r)	c=i, r=dp[i];
		
		rez+=1LL*dp[i]/2;
	}*/

	
	fout<<rez<<"\n";
	return 0;
}