Cod sursa(job #2843567)

Utilizator Savu_Stefan_CatalinSavu Stefan Catalin Savu_Stefan_Catalin Data 2 februarie 2022 17:44:54
Problema PScPld Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <fstream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
ifstream in("pscpld.in");
ofstream out("pscpld.out");
char s[2000055],s2[2000055];
int st,dr,n,z[1000055],i,ma;
int main()
{
    in.getline(s,1000035);
    st=dr=0;
    n=strlen(s);
    for (i=0;i<n;++i)
    {
        s2[2*i+1]=s[i];
        s2[2*i]='#';
    }
    s2[2*n]='#';
    n=2*n+1;
    for (i=0;i<n;++i)
        s[i]=s2[i];
    z[0]=0;
    for (int i=1;i<n;++i)
    {
        if (dr<i) {while (i+z[i]<n-1&&i>z[i]&&s[i+z[i]+1]==s[i-z[i]-1]) {z[i]++;} st=i-z[i]; dr=i+z[i];}
        else if (dr>=i&&dr<=i+z[(dr-i)+st]) {z[i]=dr-i; while (i+z[i]<n-1&&i>z[i]&&s[i+z[i]+1]==s[i-z[i]-1]) z[i]++; st=i-z[i]; dr=i+z[i];}
        else {z[i]=z[(dr-i)+st];}
        ma+=((z[i]+1)/2);
    }
    out<<ma;
    return 0;

}