Longest_Palindrome.cpp

#include <bits/stdc++.h>
using namespace std;
// First you make it work, then you can always make it beautiful

struct manacher {
    int n;
    string t;
    vector<int> p;
    void build(string s) {
        t.clear();
        for(auto ch : s) {
            t += '#';
            t += ch;
        }
        t += '#';
        compute(t);
    }

    void compute(string t) {
        n = t.size();
        p.assign(n, 1);
        int l = 1, r = 1;
        for(int i=1;i<n;i++) {
            // mirror pos of i in l to r is l+r-i
            p[i] = max(1, min(r - i, p[l + r - i]));
            while(i + p[i] < n && i - p[i] >= 0 && t[i - p[i]] == t[i + p[i]]) {
                p[i]++;
            }
            if(i + p[i] > r) {
                l = i - p[i];
                r = i + p[i];
            }
        }
    }

    // for even length palindrome it check (i-1, i) as centre
    int getlen(int pos, bool isOdd) {
        int ind = 2 * pos + 1 + (!isOdd);
        return p[ind] - 1;
    }

    bool ispal(int l, int r) {
        int len = r - l + 1;
        return (len <= getlen((l + r) / 2, (len & 1)));
    }

};

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    string s;
    cin >> s;
    int n = s.size();
    manacher m;
    m.build(s);

    int sz = 0;
    int l = -1, r = -1;
    for(int i=0;i<n;i++) {
        int l1 = m.getlen(i, 1);
        int l2 = m.getlen(i, 0);
        if(l1 > sz) {
            sz = l1;
            l = i - l1/2;
            r = i + l1/2;
        }
        if(l2 > sz) {
            sz = l2;
            l = i - (l2-1) / 2;
            r = i + l2 / 2;
        }
    }

    string res;
    for(int i=l;i<=r;i++) {
        res += s[i];
    }

    cout << res << "\n";
    

    return 0;
}