Cod sursa(job #928838)

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

int main(void){
    ifstream fin("pscpld.in");
    ofstream fout("pscpld.out");
    fin>>sir;
    n=sir.length();
    for (i=0; i<n; ++i) s[2*i+1]=int(sir[i]);
     s[0]=-1;
    a[1]=1; a[2*n-1]=1; rez=2;
    for (i=2; i<2*n-1; ++i) {
     if (ultim[i]==0) {
                      int l=i-1,r=i+1,lung=0;
                      while (s[l]==s[r]) {
                            ++lung; ultim[r]=i;
                            ++r; --l;
                            }
                      a[i]=2*lung+1; 
                      }
     else {
          int pos=i-2*(i-ultim[i]);
          int brat=min(ultim[i]+a[ultim[i]]/2-i+1,a[pos]/2+1);
          if (i+brat>=2*n){
                            a[i]=2*(2*n-1-i)+1;
                            int r=i+1;
                            while (r<2*n) { ultim[r]=i; ++r; }
                            }
          else {
            a[i]=2*(brat-1)+1;   
              int l=i-brat,r=i+brat,lung=0;
            while (s[l]==s[r]) {
                            ++lung; ultim[r]=i;
                            ++r; --l;
                            }
               a[i]+=2*lung;
               }
            }
    
     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);
}