Cod sursa(job #928975)

Utilizator ctlin04UAIC.VlasCatalin ctlin04 Data 26 martie 2013 19:41:45
Problema PScPld Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include<fstream>
#include<string>
using namespace std;
int i,n,rez,a[2000005],u,lim;
string sir;
char s[2000005];

int main(void){
    ifstream fin("pscpld.in");
    ofstream fout("pscpld.out");
    getline(fin,sir);
    n=sir.length();
    for (i=0; i<n; ++i){ s[2*i+1]=sir[i]; s[2*i]='.'; }
     s[0]='?'; lim=1; u=1;
    a[1]=1; a[2*n-1]=1; rez=2;
    
    for (i=2; i<2*n-1; ++i) {
    
       if (i>lim){
               int l=i-1,r=i+1,lim=i,u=i,lung=0;
               while (s[l]==s[r]) { ++lim; ++r; ++lung; --l; }
               a[i]=2*lung+1;
               } 
       else {
          int pos=u-(i-u);
          int brat=min(lim-i,a[pos]/2+1);  
             
             int l=i-brat,r=i+brat,lung=0;
           while (s[l]==s[r]) {
                            ++lung;
                            ++r; --l;
                            }
               a[i]+=2*lung;
               if (r>lim) { lim=r; u=i; }
            }
    
     if (i%2==1) rez+=(a[i]-1)/4+1;
      else { int val=(a[i]-1)/2;
             if (val%2==0) rez+=val/2; else rez+=val/2+1;
             }
             
      }
  fout<<rez;
 return(0);
}