Cod sursa(job #1697931)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 3 mai 2016 12:02:03
Problema PScPld Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 0.85 kb
///Abuzul de STL dauneaza grav sanatatii
#define NMAX 1000010
#include <stdio.h>

char s[2*NMAX], str[NMAX];
int  p[2*NMAX];

int main(void) {
    FILE *fin  = fopen("pscpld.in", "r");
    FILE *fout = fopen("pscpld.out", "w");
    char t;
    int i, j, n, c, r, buff;
    long long ans;

    fgets(str, NMAX, fin);

    c = r = n = ans = buff = 0;
    s[0]='+';
    while((t=str[buff++])!='\n') {
        s[++n] = '.';
        s[++n] = t;
    }
    s[++n]='.';
    s[++n]='-';

    for(i=1; i<n; ++i) {
        j=c+c-i;
        p[i]=(r>i)?min(r-i, p[j]):0;
        while(s[i+p[i]+1]==s[i-p[i]-1])
            ++p[i];
        if(i+p[i]>r) {
            c = i;
            r = i+p[i];
        }
        ans+=(p[i]+1)>>1;
    }
    fprintf(fout,"%lld\n",ans);
    return 0;
}

inline int min(int a, int b) {
    return (a<b)?a:b;
}