Manacher algorithm. Link to algorithm Implementation of solution

You can do it by prefix function of KMP algorithm.

int prefix_function(const string& s)
{
    string a = s;
    reverse(a.begin(), a.end());
    a = s + "#" + a;
     c = 0;
    for (int i = 1; i < (int)a.size(); i++)
    {
        while (c != 0 && a[c] != a[i])
            c = pref[c - 1];
        if (a[c] == a[i])
            c++;
        pref[i] = c;
    }
    return c;
}

The prefix function for this string is defined as an array π of length n, where π[i] is the length of the longest proper prefix of the substring s[0…i] which is also a suffix of this substring.

So when I appended the reverse of the string in the same string. So the prefix function value for the last index returns the longest proper prefix which is same as proper suffix (thereby a plaindrome because the string is reversed)

Do let me know if you have any further doubt! Please upvote if you find it useful and short algorithm.

You often can solve string problems without any smart functions (like zet or prefix): just use hashing!

If a substring is the answer then it is equal to a prefix. So, we can use this prefix as an answer (I hope that I understood the problem correctly).

Let's iterate over the length of the prefix. We can check whether this prefix is a palindrome or not using hashes of the given string and of the reverse string. The largest prefix is the answer.

1. Use hash, but hash might be hacked, despite that, Hashing requires at least $$$O(n\log n)$$$ pre-calc and during the query, we do something like ST table(I'm not sure if it is called that way) and can get the longest palindromic substring in $$$O(\log n)$$$, specifically, we pre-calc the hash value of $$$[l,l+2^i)$$$ by merging $$$[l,l+2^{i-1})$$$ and $$$[l+2^{i-1},l+2^{i-1}+2^{i-1})$$$

2. Use KMP, it can calculate the longest length of string that is both prefix and subfix of a substring(sorry for my poor English)

Hope to help you.