solved 'Shortest Palindrome' on LeetCode https://leetcode.com/problems/shortest-palindrome/

shortest_palindrome_brute.cpp

#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>

using namespace std;

// From https://leetcode.com/discuss/36807/c-8-ms-kmp-based-o-n-time-%26-o-n-memory-solution?show=40650#a40650
// O(n^2), 4ms.
// May fail test cases such as "abababababababababababababababababababababab".
class Solution {
 public:
  string shortestPalindrome(string s) {
    int len = s.size(), palindrome_center = 0;
    // Edge cases.
    if (len <= 1) {
      return s;
    }
    
    int longest_palindrome_size;
    while (palindrome_center <= len / 2) {
      int start = palindrome_center, 
          end = palindrome_center;
      // Move pointers to both ends of the string of same character.
      for (; end < len - 1 && s[end + 1] == s[end]; ++end) { }
      // Advance the center of potential palindrome.
      palindrome_center = end + 1;
      // Check whether is a palindrome.
      while (end < len && start >= 0 && s[end] == s[start]) {
        ++end;
        --start;
      }
      // Only when `start` is -1 we know the palindrome is a prefix.
      if (start == -1) {
        longest_palindrome_size = end;
      }       
    }
    string prefix(s.rbegin(), s.rbegin() + len - longest_palindrome_size);
    return prefix + s;
  }
};
  
int main(int argc, char *argv[]) {
  Solution sol;
  string p, res;
  
  p = "";
  res = sol.shortestPalindrome(p);
  assert(res == "");  
  
  p = "a";
  res = sol.shortestPalindrome(p);
  assert(res == "a");
  
  p = "ab";
  res = sol.shortestPalindrome(p);
  assert(res == "bab");

  p = "aacecaaa";
  res = sol.shortestPalindrome(p);
  assert(res == "aaacecaaa");
  
  p = "abcd";
  res = sol.shortestPalindrome(p);
  assert(res == "dcbabcd");
}

shortest_palindrome_kmp.cpp

#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>

using namespace std;

// From https://leetcode.com/discuss/36807/c-8-ms-kmp-based-o-n-time-%26-o-n-memory-solution
// O(n) time O(n) space, 8ms.
class Solution {
 public:
  string shortestPalindrome(string s) {
    int len = s.size(), palindrome_center = 0;
    // Edge cases.
    if (len <= 1) {
      return s;
    }
    
    // A funny way to find out the longest palindrome prefix.
    // Note the trick of "$" cuts the combined string such that
    // the last element of `next` array guarantees to point to the
    // last element of palindrome prefix.
    string combined_s = s + "$" + string(s.rbegin(), s.rend());
    int combined_len = combined_s.size();
    // KMP, see http://yo.edfward.me/2013/08/mo-kmp-suan-fa.html
    vector<int> next(combined_len + 1, 0);
    next[0] = -1;
    int i = 1, j = 0;
    while (i < combined_len) {
      if (j == -1 || combined_s[i] == combined_s[j]) {
        next[++i] = ++j;
      } else {
        j = next[j];
      }
    }
    
    int palindrome_prefix_sz = next[combined_len - 1] + 1;
    string prefix(s.rbegin(), s.rbegin() + len - palindrome_prefix_sz);
    return prefix + s; 
  }
};
  
int main(int argc, char *argv[]) {
  Solution sol;
  string p, res;
  
  p = "";
  res = sol.shortestPalindrome(p);
  assert(res == "");  
  
  p = "a";
  res = sol.shortestPalindrome(p);
  assert(res == "a");
  
  p = "ab";
  res = sol.shortestPalindrome(p);
  assert(res == "bab");

  p = "aacecaaa";
  res = sol.shortestPalindrome(p);
  assert(res == "aaacecaaa");
  
  p = "abcd";
  res = sol.shortestPalindrome(p);
  assert(res == "dcbabcd");
}

shortest_palindrome_recursion.cpp

// From https://leetcode.com/discuss/51223/my-7-lines-recursive-java-solution
// An elegant algorithm which needs some thinking.
class Solution {
 public:
  string shortestPalindrome(string s) {
    int len = s.size();
    // Edge cases.
    if (len <= 1) {
      return s;
    }
    
    int start = 0;
    for (int i = len - 1; i >= 0; --i) {
        if (s[i] == s[start]) {
            ++start;
        }
    }
    
    if (start == len) {
        return s;
    }
    string suffix = s.substr(start);
    return string(suffix.rbegin(), suffix.rend()) + 
            shortestPalindrome(s.substr(0, start)) + suffix;
  }
};