Cod sursa(job #1960570)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 10 aprilie 2017 15:33:26
Problema PScPld Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <bits/stdc++.h>
#define MAXN 1000002
int len[2*MAXN+1];
char v[2*MAXN+1];
int main(){
    FILE*fi,*fout;
    int i,n,k;
    char ch;
    fi=fopen("pscpld.in" ,"r");
    fout=fopen("pscpld.out" ,"w");
    ch=fgetc(fi);
    n=0;
    while(isalpha(ch)){
       v[++n]='*';
       v[++n]=ch;
       ch=fgetc(fi);
    }
    v[n+1]='*';
    k=0;
    for(i=1;i<=n+1;i++){
        if(k+len[k]<=i)
          len[i]=1;
        else
          len[i]=std::min(len[2*k-i],k+len[k]-i);
        while(i-len[i]>0&&i+len[i]<=n+1&&v[i-len[i]]==v[i+len[i]])
          len[i]++;
        if(i+len[i]>k+len[k])
          k=i;
    }
    long long ans=0;
    for(i=1;i<=2*n+1;i++)
      ans+=len[i]/2;
    fprintf(fout,"%lld" ,ans);
    fclose(fi);
    fclose(fout);
    return 0;
}