Cod sursa(job #2596027)

Utilizator valentinchipuc123Valentin Chipuc valentinchipuc123 Data 9 aprilie 2020 01:33:54
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.48 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("pscpld.in");
ofstream g("pscpld.out");

int manacher[2000002],st,dr,n,j;
long long sol=1;
string s;

int main()
{
f>>s;
n=s.length();
manacher[1]=1; st=1; dr=2;
///rezolvare
for(int i=2;i<2*n;i++)  {

     j = min(manacher[st-(i-st)],max(dr-i,0)) ;
        for(;i+j<2*n&&i>j&&((i+j)%2||s[(i+j+1)/2]==s[(i-j-1)/2]);j++);
     if(i+j>dr)
      st=i, dr=i+j;
     manacher[i]=j;
     sol+=j/2+j%2;
   }
g<<sol;
}