Cod sursa(job #2203608)

Utilizator Luca19Hritcu Luca Luca19 Data 12 mai 2018 18:54:58
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <fstream>
#include <cstring>
#define Nmax 100005

using namespace std;

ifstream f("pscpld.in");
ofstream g("pscpld.out");

int man[2*Nmax], n;
char a[Nmax], x;
long long ans, len;

void read()
{
    while ( f >> x )
    {   len++;
        a[len]=x;
        len++;
        a[len]='#';
    }
    len--;
}

void manachers()
{
    int mid=1, rgt=1;
    man[1]=1;
     for ( int i = 1 ; i < n ; i ++ )
     {
            man[i]=min(rgt-i+1, man[2*mid-i]);

         while ( (a[i+man[i]]==a[i-man[i]]) && (i-man[i]>=0) && (i+man[i]<=n+1) )
            man[i]++;

         if ( i+man[i] >= rgt )
          {
              mid=i;
              rgt=i+man[i]-1;
          }
     }
}

void solve()
{
  for ( int i = 1 ; i <= len ; i ++ )
     {
         man[i]=man[i]/2+i%2;
         ans+=man[i];
     }
     g << ans;
}

int main()
{
    read();
    manachers();
    solve();

    return 0;
}