Cod sursa(job #1752417)

Utilizator DjokValeriu Motroi Djok Data 3 septembrie 2016 20:02:10
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.64 kb
#include<bits/stdc++.h>
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=l=-1,i=0;i<n;++i)
  {
    k=(i>r) ? 1:min(d1[l+r-i],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=l=-1,i=0;i<n;++i)
  {
    k=(i>r) ? 0:min(d2[l+r-i+1],r-i+1);
    while(i+k<n && i-k-1>=0 && s[i+k]==s[i-k-1]) ++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;
}