Cod sursa(job #891819)

Utilizator simpleBereczki Cristian simple Data 25 februarie 2013 20:22:34
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include<cstdio>
#include<cstring>
char b[1000001],a[2000001];
int n,i,lg=1,poz=1,lung[2000001];
long long nr;
int minimum(int a,int b)
{
    if(a<b) return a;
    return b;
}
int main()
{
    freopen("pscpld.in","r",stdin);
    freopen("pscpld.out","w",stdout);
    gets(b);
    nr=1;
    n=strlen(b);
    for(i=0;i<n;i++){
        a[2*i+1]=b[i];
        a[2*i]=' ';}
    n=2*n-1;
    lung[0]=1;
    lung[1]=1;
    for(i=2;i<=n;i++){
        lung[i]=1;
        if(poz+lg-1>i)
            lung[i]=minimum(poz+lg-i,lung[2*poz-i]);
        while(i-lung[i]>0 && a[i-lung[i]]==a[i+lung[i]])
            {lung[i]++;
            }
        if(i%2)
            nr+=(lung[i]+1)/2;
        else
            nr+=lung[i]/2;
        if(lung[i]+i>poz+lg) poz=i;lg=lung[i];}
    printf("%I64d\n",nr);
    fclose(stdout);
    return 0;
}