Manacher's Algorithm | LeetCode The Hard Way

A famous algorithm and the fastest known technique to find palindromic substrings of even or odd length.

Please refer the tutorial guide for more details.

The function takes input of a string and returns all possible palindromic strings at each center, possible in the string.

vector<string> palindromicSubstrings(string s) {
    if (s.empty()) return {};

    // Convert odd/even strings to odd
    string str = "";
    for (int i = 0; i < s.length() - 1; i++) {
        str += s[i];
        str += "#";
    }
    str += s[s.length() - 1];

    // Initializing variables
    int len = str.length();
    vector<int> pLengths(len, 0);
    int c = 0;
    int R = 0;

    for (int i = 0; i < len; i++) {
        // Mirroring the palindromic length
        if (i < R) {
            int mirror = 2 * c - i;
            pLengths[i] = min(R - i, pLengths[mirror]);
        }

        // Exploring beyond bounds
        while (i - pLengths[i] - 1 >= 0 && i + pLengths[i] + 1 < len &&
               str[i + pLengths[i] + 1] == str[i - pLengths[i] - 1]) {
            pLengths[i]++;
        }

        // Update center and bound
        if (pLengths[i] + i > R) {
            c = i;
            R = i + pLengths[i];
        }
    }

    // Return all possible palindromic strings
    vector<string> strings;
    for (int i = 0; i < len; i++) {
        string palindrome = str.substr(i - pLengths[i], 2 * pLengths[i] + 1);
        string result = "";
        for (char ch : palindrome) {
            if (ch != '#') {
                result += ch;
            }
        }
        strings.push_back(result);
    }

    return strings;
}