Cod sursa(job #2955522)

Utilizator doruliqueDoru MODRISAN dorulique Data 17 decembrie 2022 12:02:39
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.8 kb
/**
  Citim un string cu maxim 1 milion de carctere, doar litere
mici.
  Afișăm vectorul razelor determinat din algoritmul lui
Manacher.
*/
#include <iostream>
#include <fstream>
using namespace std;

char q[1000001],s[2000010];
int rz[2000010];
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
int main()
{
    fin>>q;
    int i,nc=0,l,r;
    s[nc++]='#';
    for(i=0;q[i];i++)
    {
        s[nc++]=q[i];
        s[nc++]='#';
    }
    s[nc]=0;
    l=r=-1;
    for(i=0;i<nc;i++)
    {
      if(i>r)rz[i]=0;
      else rz[i]=min(rz[l+r-i],r-i);
      while(i-rz[i]>=0 && s[i-rz[i]]==s[i+rz[i]])
        rz[i]++;
      rz[i]--;
      if(i+rz[i]>r) l=i-rz[i],r=i+rz[i];
    }
    long long sum=0;
    for(i=0;i<nc;i++)sum+=(rz[i]+1)/2;
    fout<<sum;
    return 0;
}