Cod sursa(job #2157232)

Utilizator Garen456Paun Tudor Garen456 Data 9 martie 2018 13:36:06
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
char s[1000005],d[2000005];
int b[2000005],ct;
long long sol;
int main()
{   int i,n,ct=0,l,r,mid;
     fin>>s;
     n=strlen(s);
     d[++ct]='A';
    for(i=0;i<n;++i)
    { d[++ct]=s[i];
       d[++ct]='A';
    }
    l=r=mid=1;

    for(i=2;i<=ct;++i)
    { if(i>r) l=r=mid=i;
       else
       {
         b[i]=b[2*mid-i];
         if(b[i]+i>=r)
         { b[i]=r-i;
           mid=i;
           l=mid-b[i];
         }
       }
      while(l-1>=1 && r+1<=ct && d[l-1]==d[r+1])
      { b[mid]++;
          l--; r++;
      }
    }
    for(i=1;i<=ct;++i)
       if(i%2)
        sol=sol+b[i]/2;
       else sol=sol+b[i]/2+1;

   fout<<sol;
    return 0;
}