Cod sursa(job #123271)

Utilizator gabitzish1Gabriel Bitis gabitzish1 Data 15 ianuarie 2008 11:23:09
Problema PScPld Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <stdio.h>
#include <string.h>
char s[1000000];
int n, contor, v[1000000];

void citire()
{
   freopen("pscpld.in","r",stdin);
   freopen("pscpld.out","w",stdout);
   fgets(s,1000000,stdin);
   n = strlen(s);
   s[n - 1] = NULL;
   n--;
}

void Dinamic()
{
   int i, j, l, r;
   for (i = 0; i < n; i++) v[i] = i + 1;
   contor = 1;

   for (i = 1; i < n; i++)
   {
      l = r = i;
      while (s[l] == s[r])
      {
	if (v[r] > v[l - 1] + 1)  v[r] = v[l - 1] + 1;
	l--;
	r++;
	if (l != r)  contor++;
      }
      l = i - 1; r = i;
      while (s[l] == s[r])
      {
	if (v[r] > v[l - 1] + 1) v[r] = v[l - 1] + 1;
	contor++;
	l--;
	r++;
      }
   }
   printf("%d\n",contor);
}

int main()
{
   citire();
   Dinamic();
   return 0;
}