Cod sursa(job #2763508)

Utilizator cadmium_Voicu Mihai Valeriu cadmium_ Data 14 iulie 2021 17:47:09
Problema PScPld Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.82 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++) {
    int& r=afd[i];
    if(i>rmost)
      r=1;
    else {
      r=afd[lmost+rmost-i];
    }
    while(r<=i && i+r<n && s[i+r]==s[i-r])
      r++;
    r--;
    if(i+r>rmost) {
      rmost=i+r;
      lmost=i-r;
    }
    if(s[i]=='|')
      total+=(r+1)/2;
    else
      total+=r/2+1;
  }
  //for(i=0; i<n; i++)
    //cout << s[i] <<' ';
  //for(i=0; i<n; i++)
    //cout << afd[i] <<' '; 
  cout << total << '\n';
  return 0;
}