EasyPalindrome

In our virtual land, there's a company named evil corp and a character named Mr Robot.

He is planning to take the evil corp down. He planned to do so by hacking their servers and destroying their data. In order to pull off the hack, he needs the key but the key is hidden in a string S. Help him get the key.

You are given a string S of length N  consisting of lowercase letters. The key is made up of 2 parts.
Key= Depth + last string

1.>Depth is the number of times you can successfully divide the string.

You can divide the string S if and only if it is a palindrome of even length.
Also, you can only divide the string into 2 strings of equal length and after dividing, the string S becomes equal to its 1st half.
For eg: 
S= "abba" => after dividing => S="ab"

2.>last string is the smallest possible string formed by dividing the string S repeatedly until the length of the string S becomes odd.

You can take the help of Mr. Robot anytime you want including 0.
Mr. Robot helps you by replacing the string S with its longest palindromic substring.
For eg S="abcabbacb" => S="bcabbacb".

The longest palindromic substring of a string is the substring which can be read in the same way from both sides(front and back) and is of the longest possible length.
If there is a tie, then he chooses the one which occurs first in the string S.

Example:

Input:  n = 4,  s = "aaaa"

Output:

2
a

Approach:

C++

#include <bits/stdc++.h>
using namespace std;

#define SIZE 1000000
int co = 0;

string convert(string s)
{

    string new_string = "@";
    for (int i = 0; i < s.size(); i++)
    {
        new_string += "#" + s.substr(i, 1);
    }
    new_string += "#$";
    return new_string;
}
void longestPalindrome(string s)
{
    int p[3 + s.size() * 2] = {0};
    string q = convert(s);

    int c = 0, r = 0;
    int i;
    for (i = 1; i < q.size() - 1; i++)
    {
        int m = c - (i - c);
        if (r > i)
        {
            p[i] = min(r - i, p[m]);
        }
        while (q[i + 1 + p[i]] == q[i - 1 - p[i]])
        {
            p[i]++;
        }
        if (i + p[i] > r)
        {
            c = i;
            r = i + p[i];
        }
    }
    p[q.size() - 1] = 0;
    int maxPalindrome = 0;
    int centerIndex = 0;

    for (i = 1; i < q.size() - 1; i++)
    {
        if (p[i] > maxPalindrome)
        {
            maxPalindrome = p[i];
            centerIndex = i;
        }
    }
    if (maxPalindrome % 2 == 0)
    {
        string x = s.substr((centerIndex - 1 - maxPalindrome) / 2, maxPalindrome / 2);
        co++;
        return longestPalindrome(x);
    }
    else
    {
        cout << co << "\n"
             << s.substr((centerIndex - 1 - maxPalindrome) / 2, maxPalindrome);
        return;
    }
}
int main()
{

    int n = 4;

    string s = "aaaa";

    longestPalindrome(s);
    return 0;
}