⬅ Manacher's Algorithm | A Helpful Line-by-Line Code Tutorial and Explanation

#include <iostream>
#include <cstring>
using namespace std;
 
char* getSubstring(char c[], int starting, int ending){
 
    int length = ending - starting + 1;
    int temp = length;
 
    if(ending < starting){
        return "null";
    }
 
    if(length > strlen(c)){
        return "null";
    }
 
    char* str = new char[length + 1];
 
    char *p1 = str;
    char *p2 = &c[starting];
 
    while(temp--){
        *(p1++) = *(p2++);
    }
 
    *p1 = '\0';
 
    return str;
 
}
 
char* preProcess(char c[]){
 
    int length = strlen(c);
 
    char* str = new char[2 * strlen(c) + 1];
    char* temp = str;
 
    *(temp++) = '#';
    for(int i = 0; i < length; i++){
        *(temp++) = c[i];
        *(temp++) = '#';
    }
 
    *temp = '\0';
 
    return str;
 
}
 
char* postProcess(char c[]){
 
    int length = strlen(c);
 
    char* str = new char[length];
    char* temp = str;
 
    for(int i = 0; i < length; i++){
        if(c[i] != '#'){
            *(temp++) = c[i];
        }
    }
 
    *temp = '\0';
 
    return str;
 
}
 
int main(){
 
    char* str = preProcess("jklollolkidding");
    int length = strlen(str);
 
    int *P = new int[length];
 
    int C = 0;
    int R = 0;
 
    for(int i = 0; i < length; i++){
 
        int i_mirror = C - (i - C);
 
        if(R > i){
            P[i] = min(R - i, P[i_mirror]);
        }else{
            P[i] = 0;
        }
 
        while (str[i + 1 + P[i]] == str[i - 1 - P[i]]){
            P[i]++;
        }
 
        if (i + P[i] > R) {
          C = i;
          R = i + P[i];
        }
 
    }
 
    int maxLen = 0;
    int centerIndex = 0;
    for (int i = 1; i < length - 1; i++) {
        if (P[i] > maxLen) {
            maxLen = P[i];
            centerIndex = i;
        }
    }
 
    cout << postProcess(getSubstring(str, centerIndex - maxLen, centerIndex + maxLen)) << endl;
 
return 0; }