7D - Palindrome Degree - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;

typedef std::pair<int, int> PII;
char c[5000001];
char p[10000010];
int arm[10000010];
int edge=0;
int md=0;
int cs;
int manacher() {
    cs=strlen(c+1);
    for(int i=1;i<=cs;i++){
        p[2*i-1]='?';
        p[2*i]=c[i];
    }
    p[2*cs+1]='?';
    arm[1]=1;
    md=1;
    edge=1;
    for(int i=2;i<=2*cs+1;i++){
        arm[i]=1;
        if(i<=edge){
            arm[i]=arm[2*md-i];
            if(arm[i]+i-1<edge) continue;
            else arm[i]=edge-i+1;
        }
        while((i-arm[i]>0&&i+arm[i]<=2*cs+1)&&p[i+arm[i]]==p[i-arm[i]]) arm[i]++;
        md=i,edge=i+arm[i]-1;
    }
    int ans=0;
    for(int i=1;i<=2*cs+1;i++)
    ans=max(ans,(2*arm[i]-1)/2);
    return ans;
}

int main() {
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>c+1;
    manacher();
    int mid=0,len=0;
    int ans=0;
    for(int i=2;i<=2*cs;i+=2){
        len=i+1;
        mid=(len+1)/2;
        int t=0;
        while(mid>1&&2*arm[mid]-1==len){
            if(mid&1) len=(len+1)/2;
            else len=len/2;
            mid=(mid+1)/2;
            t++;
        }
        //cout<<t<<'\n';
        ans+=t;
    }
    cout<<ans<<'\n';
    return 0;
}