Cod sursa(job #755781)

Utilizator scipianusFMI Ciprian Olariu scipianus Data 7 iunie 2012 11:31:32
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include<fstream>
using namespace std;
char v[1000100],s[2000100];
int n,Lg[2000100];
long long sol;

int main()
{
	int i,st,dr,poz;
	ifstream fin("pscpld.in");
	fin>>v;
	fin.close();
	
	n=0;
	s[++n]='*';
	for(i=0;v[i]!=0;i++)
	{
		s[++n]=v[i];
		s[++n]='*';
	}
	
	st=1;
	dr=3;
	Lg[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])
			{
				Lg[i]++;
				st--;
				dr++;
			}
		}
		else
		{
			poz=st+(dr-i);
			if(i+Lg[poz]<dr)
				Lg[i]=Lg[poz];
			else
			{
				Lg[i]=dr-i;
				st=i-Lg[i];
				dr=i+Lg[i];
				while(st>1 && dr<n && s[st-1]==s[dr+1])
				{
					Lg[i]++;
					st--;
					dr++;
				}
			}
		}
	}
	for(i=1;i<=n;i++)
		sol+=(long long)((Lg[i]+1)/2);
	
	ofstream fout("pscpld.out");
	fout<<sol<<"\n";
	fout.close();
	return 0;
}