Cod sursa(job #1125401)

Utilizator dutzulBodnariuc Dan Alexandru dutzul Data 26 februarie 2014 17:19:37
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <iostream>
#include <fstream>
using namespace std;

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

#include <cstring>
#define ll long long
#define LE 2000666
#define cout g

string s,S;
int i,pal[LE];

int main()
{
    getline(f,s);
    S+="X ";
    int N=s.length();

    for(i=0; i<N; ++i)
    {
        S+=s[i];
        S+=" ";
    }
    S+="W";

    N=S.length();
    int st=-1,dr=-1;

    for(i=1; i<N-1; ++i)
    {
        if (i>=st&&i<=dr)
        {
            int C=(st+dr)/2;
            pal[i]=min(dr-i+1,pal[C-(i-C)]);
        }

        while (S[i+pal[i]]==S[i-pal[i]]) ++pal[i];
        if (i+pal[i]-1>dr) st=i-pal[i]+1,dr=i+pal[i]-1;
    }

    ll result=0;
    for(i=1;i<N-1;++i)
    {
       result+=(ll)pal[i]/(ll)2;
       if (S[i]!=' '&&pal[i]%2) ++result;
    }

  //  cout<<S;
  //  cout<<'\n';
  //  for(i=0;i<N;++i) cout<<pal[i]<<" ";
  //  cout<<'\n';

   cout<<result<<'\n';


    return 0;
}