Cod sursa(job #1302244)

Utilizator robertstrecheStreche Robert robertstreche Data 26 decembrie 2014 19:19:29
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <fstream>
#include <string.h>

#define lmax 1000001

using namespace std;

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

char c[lmax],v[2*lmax];

int lung,i,nr,ult,poz,l[2*lmax];
long long nrsol;

int main()
{
    f>>c;

    lung=strlen(c)-1;

    for (i=0;i<=lung;i++)
     {
         v[++nr]=c[i];
         v[++nr]=' ';
     }

    v[0]=' ';

    l[1]=1;
    ult=1;
    poz=1;

    for (i=1;i<=nr;i++)
     {
         if (ult>i)
          l[i]=min(l[2*poz-i],ult-i);
         else
          l[i]=1;

         while (v[i-l[i]]==v[i+l[i]] && i-l[i]>=0 && i+l[i]<=nr+1)
          l[i]++;

         if (i+l[i]>ult)
          {
              ult=i+l[i];
              poz=i;
          }
     }

    for (i=1;i<=nr;i++)
     nrsol+=(l[i]/2);

    g<<nrsol;

   f.close();
   g.close();
}