Cod sursa(job #2335868)

Utilizator SoranaAureliaCatrina Sorana SoranaAurelia Data 4 februarie 2019 16:24:16
Problema PScPld Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

char a[1000005];
char s[2000010];
int p[2000010];
int l,P,c,r,simi;

void addHash(){

    l=strlen(a);
    for(int i=0; i<l; i++){
        s[2*i] = '#';
        s[2*i+1] = a[i];
    }
    s[2*l]='#';
    P=2*l+1;
}
int main()
{
    freopen("pscpld.in","r",stdin);
    freopen("pscpld.out","w",stdout);
    scanf("%s",a);
    addHash();
    long long vmax=0;
    for(int i=1; i<P; i++){
        simi=c-(i-c);
        if(i<=r)///decat cea mai din dreapta parte
            p[i]=min(r-i,p[simi]);
        while( i+1+p[i]<P && i-1+p[i]>=0 && s[i+1+p[i]]==s[i-1-p[i]]){
            p[i]++;
        }
        if(i+p[i]>r)
        {
            c=i;
            r=i+p[i];
        }
        vmax=vmax+1LL*(p[i]+1)/2;

    }
    printf("%d",vmax);
    return 0;
}