Cod sursa(job #2289084)

Utilizator SoranaAureliaCatrina Sorana SoranaAurelia Data 24 noiembrie 2018 10:59:37
Problema PScPld Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1 kb
#include <cstdio>
#include <algorithm>
#include <string.h>

using namespace std;
char s[3000000];
int n, c, r; ///n=strlen c= centrul palindromului r=raza

void citire()
{
    char c1;
    scanf("%c", &c1);
    while(c1<='z' && c1>='a')
    {
        s[n++]='#';
        s[n++]=c1;
        scanf("%c", &c1);
    }
    s[n++]='#';
}

int p[3000000]={0};///sirul in  care retii palindrom
int nr;
void manacher()
{
    int c=0;
    int r=0;
    for(int i=0; i<n; i++)
    {
        int ok=0;
        int simi=c-(i-c);
        p[i]=0;
        //if(r>i)
        //    p[i]=min(r-1,p[simi]);
        while(s[i+1+p[i]]==s[i-1-p[i]])
        {
            if(s[i+1+p[i]]=='#')
                nr++;
            p[i]+=1;
        }
        if(i+p[i]>r)
        {
            r=i+p[i];
            c=i;
        }
    }
}


int main()
{
    freopen("pscpld.in","r",stdin);
    freopen("pscpld.out","w",stdout);

    citire();
    manacher();
    printf("%d",nr);
    return 0;
}