Cod sursa(job #2122443)

Utilizator andreigasparoviciAndrei Gasparovici andreigasparovici Data 5 februarie 2018 08:28:08
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

char s[1000001];

int LPS[2000002];

int c, r, n;

long long int k;

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

  n=2*strlen(s)+1;


  LPS[0]=0;
  LPS[1]=1;
  c=1;
  r=2;

  for(int i=2;i<=n;i++)
  {
    int mirror = 2*c - i;
    bool expand = 0;

    if(r<=i)
    {
      LPS[i]=0;
      expand = 1;
    }
    else
    {
      if(LPS[mirror] < r-i)
      {
        LPS[i]=LPS[mirror];
      }
      else
      {
        LPS[i] = min(LPS[mirror],r-i);
        expand = 1;
      }
    }

    if(expand)
    {
      while(i-LPS[i]>0  && i+LPS[i]<n)
      {
        if((i-LPS[i]-1)%2==0)
          LPS[i]++;
        else
        {
          if(s[(i-LPS[i]-1)/2]==s[(i+LPS[i]+1)/2])
            LPS[i]++;
          else break;
        }
      }

      if(i+LPS[i] > r)
      {
        r = i+LPS[i];
        c=i;
      }
    }
  }


  for(int i=0;i<n;i++)
  {
    if(LPS[i]%2==0)
      k+=LPS[i]/2;
    else k+=LPS[i]/2+1;
  }

  printf("%lld",k);

  return 0;
}