Cod sursa(job #928617)

Utilizator ion824Ion Ureche ion824 Data 26 martie 2013 16:09:53
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include<fstream>
#include<algorithm>
#include<string>
using namespace std;
const int NM=2000005;
string q,s;
int d[NM],p[NM]; 

int main(){
    ifstream cin("pscpld.in");
    ofstream cout("pscpld.out");
    int l,i,i1,j1,len; long long sol=0LL;
    getline(cin,q); l=q.length(); s=" ";
    for(i=0;i<l-1;++i){ s+=q[i]; s+=" "; }
    s+=q[l-1];
    
    l=2*l-1;
    //cout<<s<<'\n';
    for(i=1;i<=l;++i){
      
      if(p[i])len=d[2*p[i]-i];
        else len=0;
      i1=j1=i;                   
      while(i1-len>1 && j1+len<l && s[i1-len-1]==s[j1+len+1]){ ++len; if(!p[j1+len])p[j1+len]=i; }

      if(s[i]==' '){ d[i]=((len+1)/2)*2; sol+=(d[i]/2); }
        else { d[i]=(len/2)*2 +1; sol+=(d[i]/2)+1; }                                         
    }
    
    //for(i=1;i<=l;++i)cout<<d[i]<<' ';
    cout<<sol;
 return 0;   
}