Cod sursa(job #1528664)

Utilizator andreeainfo_dAndreea Dutulescu andreeainfo_d Data 19 noiembrie 2015 22:11:18
Problema PScPld Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <cstdio>
#include <cstring>
using namespace std;
int n,poz,i,p,ok,nr,dp[1000003];
char s[1000003];
int minim(int xx, int yy)
{
    if(xx<yy)return xx;
    return yy;
}
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++)
    {
        if(poz>=i)dp[i]=minim(poz-i+1,dp[p-(i-p)]);
        else dp[i]=1;
        while(s[i+dp[i]]==s[i-dp[i]]&&i+dp[i]<=n&&i-dp[i]>0)
        {
            dp[i]++;
        }
        nr=nr+dp[i];
        if(i+dp[i]-1>poz)
        {
            p=i;
            poz=i+dp[i]-1;
        }
    }
    p=poz=0;
    for(i=1;i<=n;i++)
        dp[i]=0;
    for(i=2;i<=n;i++)
    {
        if(poz>=i)dp[i]=minim(poz-i+1,dp[p-(i-p)]);
        while(s[i+dp[i]]==s[i-dp[i]-1]&&i+dp[i]<=n&&i-dp[i]>0)
        {
            dp[i]++;
        }
        nr=nr+dp[i];
        if(i+dp[i]-1>poz)
        {
            p=i;
            poz=i+dp[i]-1;
        }
    }
    printf("%d",nr);
    return 0;
}