Shared code

#include <bits/stdc++.h>

// #ifndef ONLINE_JUDGE
//     #include "debug/debug_template.cpp"
// #else
//     #define debug(...)
//     #define debugArr(...)
// #endif

#define ll long long
#define nl endl
#define vi vector<int>
#define vvi vector<vector<int>>
#define int long long
#define double long double
#define pb push_back
#define here cout<<"HERE"<<nl;
#define forn(i,a,n) for(int i = a; i < n; i++)
#define print(a) for(auto& e : a) cout << e << " "; cout << nl;
#define all(a) a.begin(),a.end()
#define MOD(a,b) ((a%b)+b)%b
#define yesno(b) cout << ((b)? "YES\n" : "NO\n")
template<typename T> using min_heap = std::priority_queue<T, std::vector<T>, std::greater<T>>;
using namespace std;
const int MODH1 = 1e9 + 7;
const int BASE1 = 911;
const int MODH2 = 1e9 + 9;
const int BASE2 = 3571;

struct RollingHash {
    int n;
    vector<int> H1, P1;
    vector<int> H2, P2;

    RollingHash(const string &s) {
        n = s.size();
        H1.assign(n + 1, 0);
        P1.assign(n + 1, 1);
        H2.assign(n + 1, 0);
        P2.assign(n + 1, 1);

        forn(i, 0, n) {
            int val = s[i] - 'a' + 1;
            H1[i + 1] = (H1[i] * BASE1 + val) % MODH1;
            P1[i + 1] = (P1[i] * BASE1) % MODH1;

            H2[i + 1] = (H2[i] * BASE2 + val) % MODH2;
            P2[i + 1] = (P2[i] * BASE2) % MODH2;
        }
    }

    pair<int, int> get(int l, int r) {
        int x1 = MOD(H1[r] - H1[l] * P1[r - l], MODH1);
        int x2 = MOD(H2[r] - H2[l] * P2[r - l], MODH2);
        return {x1, x2};
    }
};
void solve(){
    string s;
    cin>>s;
    RollingHash S(s), R(string(s.rbegin(), s.rend()));
    int n = s.size();
    vi ans(n , 1);
    forn(i , 0 , n){
        // i is the center of the odd sized palindrome
        int mx = min(i, n - 1 - i);        
        int l = -1, r = mx + 1;
        while (r - l > 1) {
            int mid = l + (r - l) / 2;     
            int left = i - mid;
            int len = 2 * mid + 1;
            pair<int,int> hashf = S.get(left, left + len);
            pair<int,int> hashr = R.get(n - (left + len), n - left);
            if (hashf == hashr) l = mid;
            else r = mid;
        }
        ans[i + l] = max(ans[i + l] , 2 * l + 1 );
    }
    forn(i, 0, n - 1) {
        // i is the left center of the even palindrome
        // i , i + 1 is a palindrome so check if bigger is too       
        int mx = min(i, n - 2 - i);           
        int l = -1, r = mx + 1;       
        while (r - l > 1) {
            int mid = l + (r - l) / 2;       
            int left = i - mid;
            int right = i + 1 + mid;
            int len = right - left + 1;          
            pair<int,int> hashf = S.get(left, left + len);
            pair<int,int> hashr = R.get(n - (left + len), n - left);
            if (hashf == hashr) l = mid;
            else r = mid;
        }
        if (l >= 0) {
            int left = i - l;
            int right = i + 1 + l;
            ans[right] = max(ans[right] , right - left + 1); 
            // if(i == 3){
            //     cout<< l << " "<< left <<" "<< right<<" "<< right - left + 1 << nl;;
            // }
        } 
    }
    for (int i = n - 1; i >= 1; --i) {
        ans[i-1] = max(ans[i-1], max(1LL, ans[i] - 2));
    }
    print(ans);
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    //cin >> t;
    while (t--){
        solve();
    }
    return 0;
}