Cod sursa(job #2763516)

Utilizator cadmium_Voicu Mihai Valeriu cadmium_ Data 14 iulie 2021 18:15:24
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <fstream>
//#define int long long
using namespace std;

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

int afd[2000005];

int  main() {
  int i;
  
  int n;
  
  string temp,s;
  cin >> temp;
  s="";
  for(i=0; i<temp.size()-1; i++) {
    s+=temp[i];
    s+="|"; // nu da TLE pls nu da TLE
  }
  s+=temp[temp.size()-1];
  n=s.size();
  long long lmost=-1,rmost=-1,total=0;
  for(i=0; i<n; i++) {
    long long r;
    if(i>rmost)
      r=1;
    else {
      r=min(rmost-i+1,(long long)afd[lmost+rmost-i]);
      r=min(r,(long long)min(i+1,n-i));
    }
    while(r<=i && i+r<n && s[i+r]==s[i-r])
      r++;
    afd[i]=r;
    r--;
    if(i+r>rmost) {
      rmost=i+r;
      lmost=i-r;
    }
    if(s[i]=='|')
      total+=(r+1)/2;
    else
      total+=r/2+1;
  }
  //cout << '\n';
  //for(i=0; i<n; i++)
    //cout << s[i] <<' ';
  cout << total << '\n';
  return 0;
}