1828E - Palindrome Partition - CodeForces Solution

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

vector<int> manacher(string s) {
    string t = "#";
    for (auto c : s) {
        t += c;
        t += '#';
    }
    int n = t.size();
    vector<int> r(n);
    for (int i = 0, j = 0; i < n; i++) {
        if (2 * j - i >= 0 && j + r[j] > i) {
            r[i] = std::min(r[2 * j - i], j + r[j] - i);
        }
        while (i - r[i] >= 0 && i + r[i] < n && t[i - r[i]] == t[i + r[i]]) {
            r[i] += 1;
        }
        if (i + r[i] > j + r[j]) {
            j = i;
        }
    }
    return r;
}

int main(){
    int t; cin>>t; while(t--){
        int n; cin>>n; 
        string s; cin>>s;
        auto res=manacher(s);
        vector<int> next(n+1,-1),st;
        for(int i=0;i<n;i++){
            st.push_back(i);
            //cout<<res[i]<<' ';
            while(!st.empty()&&st.back()>i-res[2*(i+1)]/2){
                next[st.back()]=2*i+2-st.back();
                st.pop_back();
            }
        }
        vector<int> dp(n+1,0);
        long long ans=0;
        for(int i=n-1;i>=0;i--){
            if(next[i]!=-1) dp[i]=dp[next[i]]+1;
            ans=ans+dp[i];
        }
        cout<<ans<<endl;
    }
}