Cod sursa(job #1757001)

Utilizator cella.florescuCella Florescu cella.florescu Data 14 septembrie 2016 10:16:19
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <cstdio>
#include <cstring>
#include <cctype>
#define MAXN 1000000

using namespace std;

int raza[2*MAXN+5];
char v[2*MAXN+5]={'#'};

int main()
{
    FILE *fin, *fout;
    long long ans;
    int n, x, r, i;
    fin=fopen("pscpld.in", "r");
    v[1]='*'; v[2]=fgetc(fin); n=2;
    while(isalpha(v[n])){
      v[++n]='*';
      v[++n]=fgetc(fin);
    }
    v[n]='$'; --n;
    fclose(fin);
    x=2; raza[2]=1; ans=1LL;
    for(i=3; i<n; i++){
      if(x+raza[x]>=i)
        if(i+raza[2*x-i]<=x+raza[x])
          r=raza[2*x-i];
        else
          r=x+raza[x]-i;
      else
        r=0;
      while(v[i+r]==v[i-r])
        ++r;
      raza[i]=--r;
      if(r+i>raza[x]+x)
        x=i;
      ans+=1LL*(raza[i]+1)/2;
    }
    fout=fopen("pscpld.out", "w");
    fprintf(fout, "%lld\n", ans);
    fclose(fout);
    return 0;
}