Cod sursa(job #2582344)

Utilizator ivan.tudorIvan Tudor ivan.tudor Data 16 martie 2020 16:56:36
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.69 kb
#include<bits/stdc++.h>
using namespace std;
const int N=1000005;
string s;
int p[2*N];
string getmform(string s){
  string rez="!#";
  for(int i=0;i<s.size();i++){
    rez+=s[i];
    rez+="#";
  }
  rez+="$";
  return rez;
}
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
int main()
{
  fin>>s;
  s=getmform(s);
  int c=0,r=0;
  for(int i=1;i<s.size()-1;i++){
    int rad=0;
    if(i<=r){
      rad=min(r-i+1,p[c-(i-c)]);
    }
    while(s[i+rad+1]==s[i-rad-1])
      rad++;
    p[i]=rad;
    if(i+p[i]-1>r){
      c=i;
      r=i+p[i]-1;
    }
  }
  long long ans=0;
  for(int i=1;i<s.size()-1;i++){
    ans+=(p[i]+1)/2;
  }
  fout<<ans;
  return 0;
}