Leetcode Shortest Palindrome problem solution

class Solution(object):
    def shortestPalindrome(self, s):
        prefix_idx = 0 
        for i in range(len(s)-1, -1, -1):
            if s[i] == s[prefix_idx ]:
                prefix_idx  += 1

        if prefix_idx == len(s):
            return s

        suffix = s[prefix_idx:]
        return suffix[::-1] + self.shortestPalindrome(s[:prefix_idx]) + suffix

class Solution {
    public String shortestPalindrome(String s) {
        String temp = s + "#" + new StringBuilder(s).reverse().toString();
        int[] next = getTable(temp);
        return new StringBuilder(s.substring(next[next.length - 1] + 1)).reverse().toString() + s;
    }

    public int[] getTable(String s) {
        int[] next = new int[s.length()];
        next[0] = -1;
        int k = -1;
        int j = 0;

        while (j < s.length() - 1) {
            if (k == -1 || s.charAt(j) == s.charAt(k)) {
                j++;
                k++;
                next[j] = k;
            } else {
                k = next[k];
            }
        }
        return next;
    }
}

class Solution {
public:
    string shortestPalindrome(string s) {
        string rev_s = s;
        reverse(rev_s.begin(), rev_s.end());
        string l = s + "#" + rev_s;
        
        vector<int> p(l.size(), 0);
        for (int i = 1; i < l.size(); i++) {
            int j = p[i - 1];
            while (j > 0 && l[i] != l[j])
                j = p[j - 1];
            p[i] = (j += l[i] == l[j]);
        }
        
        return rev_s.substr(0, s.size() - p[l.size() - 1]) + s;
    }
};

bool findLongest(char *s, int len, int index1, int index2, int *remain) {
    while (index1 >= 0 && index2 <= len - 1 && s[index1] == s[index2]) {
        index1--;
        index2++;
    }
    if (index1 == -1 && *remain > len - index2) {
        *remain = len - index2;
        return true;
    }
    return false;
}

char * shortestPalindrome(char * s){
    int index = 0, len = strlen(s);
    int remain = len - 1, new_len = 2 * len - 1;
    if (len == 0) return calloc(1, sizeof(char));
    for (int i=len/2; i>=0; --i) {
        if (findLongest(s, len, i - 1, i + 1, &remain)) break;
        if (findLongest(s, len, i - 1, i    , &remain)) break;
    }
    new_len = len + remain;
    char *result = (char*)malloc(sizeof(char) * (new_len + 1));
    for (int i=0; i<remain; i++) {
        result[i] = s[len - i - 1];
    }
    for (int i=0; i<len; i++) {
        result[remain + i] = s[i];
    }
    result[new_len] = 0;
    return result;
}