Cod sursa(job #2681721)

Utilizator PredescuSebastianIonPredescu Sebastian Ion PredescuSebastianIon Data 6 decembrie 2020 14:48:30
Problema PScPld Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("pscpld.in");
ofstream g("pscpld.out");
int z[200005];
long long sol=0;
string s,aux;
int main()
{
    f>>aux;
    for(int i=0; i<aux.size(); i++)
    {
        s+="#";
        s+=aux[i];
        sol++;
    }
    s+="#";
    int C=0,R=0;
    for(int i=1; i<s.length(); i++)
    {
        int aux=2*C-i;
        if(i>R || z[aux]>=R-i)
        {
            if(i>R)R=i;
            int k=R;
            while(k<s.length() && s[k]==s[2*i-k])
            {
                k++;
            }
            k--;
            z[i]=k-i;
            if(k>C)
            {
                C=i;
                R=k;
            }
        }
        else z[i]=z[aux];
        sol+=z[i]/2;
    }
    g<<sol<<'\n';
    return 0;
}