Cod sursa(job #62024)

Utilizator crawlerPuni Andrei Paul crawler Data 21 mai 2007 17:07:49
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <cstdio>
#include <string>

using namespace std;

#define Nmax 1000100

char v[Nmax];
int a[Nmax][2], sol, N;

void ext1(int mij)
 {
  int st,dr;
  if(a[0][mij] == 0)
   a[0][mij] = 1;

  st = mij - a[0][mij] + 1;
  dr = mij + a[0][mij] - 1;

//  printf("expandez din %d\n",mij);
//  printf("limitele temp sunt %d %d\n",st,dr);

  while(st>0 && dr<N && v[st-1] == v[dr+1])
   {
//    printf("am expandat\n");
    ++a[0][mij];
    --st; ++dr;
    a[0][dr] = a[0][st];
    if(st < dr && v[st] == v[st+1])
     a[1][dr-1] = a[1][st];
   }
 }
 

void ext2(int mij)
 {
  int st,dr;
  if(a[1][mij] == 0)
   a[1][mij] = v[mij] == v[mij+1];

  if(a[1][mij] == 0)
   return ;

  st = mij - a[1][mij] + 1;
  dr = mij + a[1][mij] ;

//  printf("expandez din %d\n",mij);
//  printf("limitele temp sunt %d %d\n",st,dr);

  while(st>0 && dr<N && v[st-1] == v[dr+1])
   {
//    printf("am expandat\n");
    ++a[1][mij];
    --st; ++dr;
    a[0][dr] = a[0][st];
    if(st < dr && v[st] == v[st+1])
     a[1][dr-1] = a[1][st];
   }
 }
 
int main()
 {
  freopen("pscpld.in","r",stdin);
  freopen("pscpld.out","w",stdout);

  fgets(v,Nmax,stdin);

  N = strlen(v) - 1;

  for(int i=0;i<N;++i)
   ext1(i), ext2(i);

  for(int i=0;i<N;++i)   
   sol += a[0][i] + a[1][i];


  printf("%d\n",sol);

/*
  fputs(v,stdout);
  for(int i=0;i<N;++i)
   printf("par %d | impar %d\n",a[1][i],a[0][i]);
*/

  return 0;
 }