LeetCode - Q214 - Shortest Palindrome

This question, despite being solvable by a simple O(n^2) algorithm, almost took 2 hours of my life.

Simply because I was trying to get sub-palindromes, when instead, I should have checked for longest prefix of original string matching the suffix of its reverse.

E.g.           s = "abcda"

              reverse of s = rev = "adcba"

         longest suffix of rev matching s = "a"

              Answer = "adcbabcda"
           


class Solution {
public:
    string shortestPalindrome(string s) {
        string rev = s;
        int n = s.size();
        reverse(rev.begin(),rev.end());
        for(int i=n;i>0;i--)
        {
            if(!strncmp(s.substr(0,i).c_str(),rev.substr(n-i,i).c_str(),i))
                return rev.substr(0,n-i)+s;
        }
        return rev+s;
    }
};