Longest Palindromic Substring

Problem

Write a function that, given an input string, locates and returns the longest sequence in the string that is a palindrome.

Solution

Every sub-string starting from the longest to the shortest needs to checked as shown below

bool is_palindrome(string const& str, size_t i,size_t n);
string max_sub_palindrome(string const& str)
   {
       size_t N = str.length();
       for(size_t n=N; n>0; --n)
       {
          for (size_t i=0; i+n <=N; ++i)
            if (is_palindrome(str,i,n))
              return str.substr(i,n);
       }
       return string();
   }

is_palindrome can be computed recursively as shown below

bool is_palindrome(string const& str, size_t i,size_t n)
   {
     if (n<=1)
       return true;
     else
       return str[i]==str[i+n-1] &&
              is_palindrome(str,i+1,n-2);
   }

The above implementation of is_palindrome has O(n) time complexity.
Thus max_sub_palindrome has O(N³) time complexity where N is the length of the string. Notice however that is_palindrome is can be memoised as follows:

class Search
{
    public:
        Search(size_t n):N(n),arr(n*n)
    { }
        bool operator() (string const& str, size_t i,size_t n)
        {
            if (n<=1)
                return true;
            else if (Get(i,n))
                return false;
            else if( str[i]==str[i+n-1])
            { 
                auto k =  operator()(str,i+1,n-2);
                if (k) 
                    return k;
                else
                {
                    Set(i,n);
                    return k;
                }
            }
            else
            {
                Set(i,n);
                return false;
            }
        }
    private:
        bool Get (size_t i, size_t j)
        {
            return arr[i*N+j-1];
        }
        void Set (size_t i, size_t j)
        {
            arr[i*N+j-1]=true;
            std::cout<<i<<","<<j<<std::endl;
        }
        std::vector<bool> arr;
        size_t N;

};

I would like to draw your attention to Line 19 and Line 25, where we flag that the sub-string commencing at i of length n is not a palindrome. We make use of that fact in Line 10 so as to avoid calling the operator() recursively if the specific problem has already been visited. We could have implemented the class as a closure in any language that supports it, which is almost all languages except C/C++.
The main function is same, save for the marked line as shown below:

string max_sub_palindrome(string const& str)
{
    size_t N = str.length();
    Search is_palindrome(N);  ///<---added     
    for(size_t n=N; n>0; --n)
    {
        for (size_t i=0; i+n <=N; ++i)
        { 
            if(is_palindrome(str,i,n))
                return str.substr(i,n);
        }
    }
    return std::string();
}