Cod sursa(job #1697928)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 3 mai 2016 11:55:05
Problema PScPld Scor 60
Compilator c Status done
Runda Arhiva de probleme Marime 0.8 kb
///Abuzul de STL dauneaza grav sanatatii
#define NMAX 1000005
#include <stdio.h>

char s[2*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;
    long long ans;

    c = r = n = ans = 0;
    s[0]='+';
    while(fscanf(fin,"%c ",&t)!=EOF) {
        s[++n] = '.';
        s[++n] = t;
    }
    s[++n]='.';
    s[++n]='-';

    for(i=1; i<n; ++i) {
        j=2*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)/2;
    }
    fprintf(fout,"%lld\n",ans);
    return 0;
}

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