Cod sursa(job #2289090)

Utilizator cristina-criCristina cristina-cri Data 24 noiembrie 2018 11:01:01
Problema PScPld Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <cstdio>
#include <algorithm>
#define NMAX 2000005

using namespace std;

char s[NMAX];
int p[NMAX], sim[NMAX];


int main()
{

    freopen("pscpld.in", "r", stdin);
    freopen("pscpld.out", "w", stdout);
    int n=0;
    s[0]='#';
    for(int i=1; n == 0; i++)
    {
        scanf("%c", &s[i]);
        if(s[i]<'a' || s[i]>'z')
        {
            n=i;
            s[i]=0;
            i-=2;
        }
        i++;
        s[i]='#';
    }
    //printf("%s", s);

    int c=0;
    int r=0;
    int ok=0, nr=0;
    for(int i=1; i<n; i++)
    {
        sim[i]=c-(i-c);
        p[i]=0;
        ok=0;
        if(r>i)
            p[i]=min(r-i, p[sim[i]]);
        while(s[i+1+p[i]] == s[i-1-p[i]])
        {
            if(s[i+1+p[i]] == '#')
                nr++;
            p[i]+=1;
            //ok=1;
        }
        if(i+p[i]>r)
        {
            r=i+p[i];
            c=i;
        }
//        if(ok==1)
//            nr+=p[i];
    }
    printf("%d", nr);
    return 0;
}