Cod sursa(job #2586192)

Utilizator betybety bety bety Data 19 martie 2020 22:23:05
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.01 kb
///pscpld

#include <bits/stdc++.h>

using namespace std;

const int N=1000005;

string s;

int p[2*N];

void dffs(int node)

{

    for(int i=1;i<=node;++i)

    if(i^(i&-i))

    dffs(i);

}

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;

}