Cod sursa(job #2798458)

Utilizator bem.andreiIceman bem.andrei Data 11 noiembrie 2021 12:10:37
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <bits/stdc++.h>

using namespace std;
ifstream r("pscpld.in");
ofstream w("pscpld.out");
int n;
int m[2000010];
string s, aux;
void manacher()
{
    int r=0, mij=0;
    for(int i=1;i<=n;i++)
    {
        if(i<r&&i+m[2*mij-i]<r)
        {
            m[i] = m[mij - (i - mij)];
            continue;
        }
        int x = 0;
        if(i<r){
            x=r-i;
        }
        while(s[i+x+1]==s[i-x-1]){
            x++;
        }
        if(i+x>r){
            r=i+x;
            mij=i;
        }
        m[i]=x;
    }
}
int main()
{
    r>>aux;
    s="#";
    for (int i=0;i<aux.size()-1;i++)
    {
        s+=aux[i];
        s+="*";
    }
    s+=aux[aux.size()-1];
    s+="$";
    n=s.size()-2;
    manacher();
    long long ans=0;
    for (int i=1;i<=n;i++)
    {
        if(i&1)
        {
            ans += (long long)(m[i] / 2 + 1);
        }
        else
        {
            ans += (long long)((m[i] + 1) / 2);
        }
    }
    w<<ans;
    return 0;
}