Cod sursa(job #62193)

Utilizator crawlerPuni Andrei Paul crawler Data 21 mai 2007 22:48:15
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <cstdio>
#include <string>
#include <algorithm>

using namespace std;

#define Nmax 1000100

char v[Nmax];
int a1[Nmax], a0[Nmax], sol, N;

void ext1(int mij);
void ext2(int mij);

int main()
 {
  freopen("pscpld.in","r",stdin);
  freopen("pscpld.out","w",stdout);

  fgets(v,Nmax,stdin);

  N = strlen(v) ;

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


  for(int i=0;i<N;++i)   
   sol += a0[i] + a1[i];

  printf("%d\n",sol);
/*
  fputs(v,stdout);
  for(int j=0;j<N;++j)
   printf("par %d | impar %d\n",a1[j],a0[j]);
  printf("\n"); 
*/

  return 0;
 }

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

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

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

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

 }

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

  if(a1[mij] == 0)
   return ;

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

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

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