Pagini recente » Cod sursa (job #74739) | Cod sursa (job #1803301) | Cod sursa (job #2790854) | Cod sursa (job #2691681) | Cod sursa (job #912622)
Cod sursa(job #912622)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
FILE *f=fopen("pscpld.in","r"),*g=fopen("pscpld.out","w");
int x[2000005],i,j,k,centru;
char aux[1000005],s[2000005];
long long ras;
int main()
{
fgets(aux,1000005,f);
int n=strlen(aux),N=-1;
for(i=0;i<n;i++)
{
s[++N]='#';
s[++N]=aux[i];
}
for(i=1,j=0;i<=N;i++)
{
if(i>j)
{
for(k=1;i+k<=N&&s[i+k]==s[i-k];k++);
x[i]=k-1;
j=i+k-1;
centru=i;
}
else
{
if(x[2*centru-i]<j-i)
x[i]=x[2*centru-i];
else
{
for(k=1;j+k<=N&&s[j+k]==s[2*i-j-k];k++);
x[i]=j-i+k-1;
}
if(j<i+x[i])
{
j=i+x[i];
centru=i;
}
}
ras+=(x[i]+1)/2;
}
fprintf(g,"%lld\n",ras);
return 0;
}