Cod sursa(job #1226785)

Utilizator mihaimusatMihai Musat mihaimusat Data 7 septembrie 2014 15:55:04
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include<fstream>

using namespace std;

char v[1000100],s[2000100];
int n,i,st,dr,poz,len[2000100];
long long sol;

int main()
{
	ifstream fin("pscpld.in");
	ofstream fout("pscpld.out");

	fin>>v;

	n=0;
	s[++n]='*';
	for(i=0;v[i]!=0;i++)
	{
		s[++n]=v[i];
		s[++n]='*';
	}

	st=1;
	dr=3;
	len[2]=1;
	for(i=3;i<=n;i++)
	{
		if(i>dr)
		{
			st=dr=i;
			while(st>1 && dr<n && s[st-1]==s[dr+1])
			{
				len[i]++;
				st--;
				dr++;
			}
		}
		else
		{
			poz=st+(dr-i);
			if(i+len[poz]<dr)
				len[i]=len[poz];
			else
			{
				len[i]=dr-i;
				st=i-len[i];
				dr=i+len[i];
				while(st>1 && dr<n && s[st-1]==s[dr+1])
				{
					len[i]++;
					st--;
					dr++;
				}
			}
		}
	}
	for(i=1;i<=n;i++)
		sol+=(long long)((len[i]+1)/2);

	fout<<sol<<"\n";

	return 0;
}