Cod sursa(job #1003851)

Utilizator cahemanCasian Patrascanu caheman Data 1 octombrie 2013 18:37:51
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include<cstdio>
#include<cstring>

using namespace std;

int pozmax1[1000005], pozmax2[1000005];
char sir[1000005];

int maxim(int a, int b)
{
  if(a < b)
    return b;
  else
    return a;
}

int minim(int a, int b)
{
  if(a > b)
    return b;
  else
    return a;
}

int main()
{
  freopen("pscpld.in", "r", stdin);
  freopen("pscpld.out", "w", stdout);
  int n, i, pozdi1 = 0, pozdi2 = 0;
  long long s = 0;
  gets(sir);
  n = strlen(sir);
  for(i = 1; i <= n; ++ i)
  {
    pozmax1[i] = 0;
    if(pozdi1 + pozmax1[pozdi1] >= i)
      pozmax1[i] = maxim(pozmax1[i], minim(pozmax1[pozdi1 + pozdi1 - i], pozdi1 + pozmax1[pozdi1] - i));
    while(i - pozmax1[i] >= 2 && i + pozmax1[i] + 1 <= n && sir[i - pozmax1[i] - 2] == sir[i + pozmax1[i]])
    {
      ++ pozmax1[i];
    }
    if(i + pozmax1[i] > pozdi1 + pozmax1[pozdi1])
      pozdi1 = i;
    s += pozmax1[i] + 1;
    pozmax2[i] = 0;
    if(pozdi2 + pozmax2[pozdi2] >= i + 1)
      pozmax2[i] = maxim(pozmax2[i], minim(pozmax2[pozdi2 + pozdi2 - i], pozdi2 + pozmax2[pozdi2] - i));
    while(i - pozmax2[i] >= 1 && i + pozmax2[i] + 1 <= n && sir[i - pozmax2[i] - 1] == sir[i + pozmax2[i]])
    {
      ++ pozmax2[i];
    }
    if(i + pozmax2[i] > pozdi2 + pozmax2[pozdi2])
      pozdi2 = i;
    s += pozmax2[i];
  }
  printf("%lld", s);
  return 0;
}