Cod sursa(job #1140052)

Utilizator binicBinica Nicolae binic Data 11 martie 2014 18:05:40
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include<cstdio>
#include<cstring>
using namespace std;
long long r,j,min,nr,n,x,y,i,dp[1000009];
char s[1000009];
int main()
{
    freopen("pscpld.in","r",stdin);
    freopen("pscpld.out","w",stdout);
    gets(s+1);
    n=strlen(s+1);
    for(i=1;i<=n;i++)
    {
        dp[i]=1;
        if(r>=i)
        {
            min=dp[j-(i-j)];
            if(min>r-i+1) min=r-i+1;
            dp[i]=min;
        }
        x=i-dp[i];
        y=i+dp[i];
        while(1)
        {
            if(s[x]==s[y]&&x>0&&y<=n)
            {
                x--;
                y++;
                dp[i]++;
            }
            else break;
        }
        if(r<dp[i]+i-1)
        {
            r=dp[i]+i-1;
            j=i;
        }
        nr+=dp[i];
    }
    r=j=0;
    for(i=1;i<=n;i++)
    {
        dp[i]=0;
        if(r>=i)
        {
            min=dp[j-(i-j)];
            if(min>r-i) min=r-i;
            dp[i]=min;
        }
        x=i-dp[i]-1;
        y=i+dp[i];
        while(1)
        {
            if(s[x]==s[y]&&x>0&&y<=n)
            {
                x--;
                y++;
                dp[i]++;
            }
            else break;
        }
        if(r<dp[i]+i)
        {
            r=dp[i]+i;
            j=i;
        }
        nr+=dp[i];
    }
    printf("%lld",nr);
    return 0;
}