Cod sursa(job #2260617)

Utilizator cyg_SerbanBFlorin Gheorghe cyg_SerbanB Data 15 octombrie 2018 11:31:47
Problema PScPld Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <cstdio>
#include <string>
#include <cstring>
using namespace std;
char s[1000005],s1[2000005];
int p[2000005];
int main()
{
    freopen("pscpld.in","r",stdin);
    freopen("pscpld.out","w",stdout);
    int n,i,j,k,m,l,lmax,r,c;
    gets(s);
    s1[0]='@';
    l=1;
    for(i=0; i<strlen(s); ++i)
    {
        s1[l++]='#';
        s1[l++]=s[i];
    }
    s1[l++]='#';
    s1[l++]='%';
    s1[l]='\n';
    r=c=0;
    for(i=1; i<l-1; ++i)
    {
        k=c-(i-c);
        if(r>i)
            p[i]=min(r-i,p[k]);
        while(s1[i+1+p[i]]==s1[i-1-p[i]])
            p[i]++;
        if(i+p[i]>r)
        {
            c=i;
            r=i+p[i];
        }
    }
    int sum=0;
    for(i=1;i<l-1;++i)
        if(p[i]>0)
        {
            if(i%2==0)
                sum=sum+p[i]/2+1;
            if(i%2==1)
                sum=sum+p[i]/2;
        }
    printf("%d",sum);
    return 0;
}