Cod sursa(job #1304056)

Utilizator DjokValeriu Motroi Djok Data 28 decembrie 2014 16:50:38
Problema PScPld Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.54 kb
#include<fstream>
#include<algorithm>
#include<string>
using namespace std;

int d[5][1000005],i,p,n,k,l,r;
long long rs;
string s;

int main()
{
  ifstream cin("pscpld.in");
  ofstream cout("pscpld.out");

  getline(cin,s); n=s.length();

  for(p=0;p<2;++p)
   for(r=-1,l=i=0;i<n;++i)
   {
     k=(i>r ? 0:min(d[p][l+r-i]-p,r-i))+1;
     while(i+k-1<n && i-k+p>=0 && s[i+k-1]==s[i-k+p]) ++k;
     d[p][i]=--k;
     if(i+k>r) l=i-k+p,r=i+k-1;
   }

  for(i=0;i<n;++i) rs+=d[0][i]+d[1][i];

  cout<<rs<<'\n';

 return 0;
}