Cod sursa(job #1304024)

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

int d1[1000005],d2[1000005],i,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(r=-1,l=i=0;i<n;++i)
  {
    k=(i>r) ? 1:min(d1[l+r-i+1]+1,r-i+1);
    while(i+k<n && i-k>=0 && s[i+k]==s[i-k]) ++k;
    d1[i]=k--;
    if(i+k>r) l=i-k,r=i+k;
  }

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

  for(i=0;i<n;++i) rs+=d1[i]+d2[i];

  cout<<rs<<'\n';

 return 0;
}