Cod sursa(job #479371)

Utilizator irene_mFMI Irina Iancu irene_m Data 23 august 2010 20:34:22
Problema PScPld Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.93 kb
#include <cstdio>
#include <string>
#define MaxN 1000005
#define infile "pscpld.in"
#define outfile "pscpld.out"

long long N,sol[MaxN],solp[MaxN],rez;
char a[MaxN];

void read()
{
      int i;

      scanf("%s",&a);
      N=strlen(a);
      for(i=N;i>=1;i--)
            a[i]=a[i-1];
}

long long minim(long long x,long long y)
{
      if(x<y)
            return x;
      return y;
}

void solve()
{
      long long lasti,lastp,l,i;

      lasti=lastp=1;
      if(a[1]==a[2])
            solp[1]=1, rez++;

      for(i=2;i<N;i++)
      {

            if(a[i-1]==a[i])
                  rez++;
            if(i<lasti+sol[lasti])
                  sol[i]=minim(sol[lasti-(i-lasti)],lasti+sol[lasti]-i);

            l=sol[i];
            if(lasti+sol[lasti]<=i+sol[i])
            {
                  lasti=i;
                  while(i-l>=1 && i+l<=N && a[i-l]==a[i+l])
                        l++;
                  if(l>=1)
                        sol[i]=l-1;
            }
            rez+=sol[i];


            //
            if(i<lastp+solp[lastp])
                  solp[i]=minim(solp[lastp-(i-lastp)], lastp+solp[lastp]-i);

            l=solp[i];
            if(lastp+solp[lastp]<=i+solp[i])
            {
                  lastp=i;
                  while(i-l>=1 && i+l+1<=N && a[i-l]==a[i+l+1])
                        l++;
                  if(l>=1)
                        solp[i]=l-1;
            }
            rez+=solp[i];
      }
}

/*void solvei()
{
      long long last=1,l,i;

      for(i=2;i<N;i++)
      {
            if(i<last+sol[last])
                  sol[i]=minim(sol[last-(i-last)], last+sol[last]-i);

            l=sol[i];
            if(last+sol[last]<=i+sol[i])
            {
                  last=i;
                  while(i-l>=1 && i+l<=N && a[i-l]==a[i+l])
                        l++;
                  if(l>=1)
                        sol[i]=l-1;
            }
            rez+=sol[i];
      }
}

void solvep()
{
      long long last=1,l,i;
      if(a[1]==a[2])
            solp[1]=1, rez++;

      for(i=2;i<N;i++)
      {
            if(i<last+solp[last])
                  solp[i]=minim(solp[last-(i-last)], last+solp[last]-i);

            l=solp[i];
            if(last+solp[last]<=i+solp[i])
            {
                  last=i;
                  while(i-l>=1 && i+l+1<=N && a[i-l]==a[i+l+1])
                        l++;
                  if(l>=1)
                        solp[i]=l-1;
            }
            rez+=solp[i];
      }

      for(i=1;i<N;i++)
            if(a[i]==a[i+1])
                  solp[i]++, rez++;
}*/

void write()
{
      rez+=N;
      printf("%lld\n",rez);
}

int main()
{
      freopen(infile,"r",stdin);
      freopen(outfile,"w",stdout);

      read();
      /*solvei();
      solvep();*/
      solve();
      write();

      fclose(stdin);
      fclose(stdout);
      return 0;
}