For this problem, KMP-based solution is a very typical and classic O(n) solution. Here is a different solution, it's also O(n), and I think it is more easy to understand.

In order to slove this problem, the key is to get the length of the longest palindromic prefix substring. if the length of s is `len`

, and the length of the longest palindromic prefix substring is `longest`

, the remaining substring will be `s.substr(longest, len - longest)`

, than we should reverse the remaining substring and adding it in front of s.

For example, if s is `"abacbbcda"`

, so the longest palindromic prefix substring is `"aba"`

(not `"cbbc"`

because it's not prefix string), and the remaining substring is `"cbbcda"`

, we reverse the remaining substring and get `"adcbbc"`

, so the result is `"adcbbc" + "abacbbcda"`

.

The follow is my c++ solution, only 4ms. Please note that the condition in for loop is `begin <= len / 2`

instead of `begin < len`

, because if `begin > len / 2`

, the substring can not be prefix string, so there is no need to continue.

**Update: I made wrong analysis, the complexity is O(N^2) but not O(N). Thanks very much for Sammax's reminder.**

```
class Solution {
public:
std::string shortestPalindrome(std::string s) {
int len = s.length();
if (len < 2)
return s;
// calculate the length of the longest palindromic prefix substring.
int longest = 1, start, end;
for (int begin = 0; begin <= len / 2;) {
start = end = begin;
while (end < len - 1 && s[end + 1] == s[end])
++end;
begin = end + 1;
while (end < len - 1 && start > 0 && s[end + 1] == s[start - 1]) {
++end;
--start;
}
// start == 0 means the palindromic substring is also prefix string.
if (start == 0 && longest < end - start + 1)
longest = end - start + 1;
}
// reverse the remaining substring and adding it in front of s.
std::string remaining = s.substr(longest, len - longest);
std::reverse(remaining.begin(), remaining.end());
return remaining + s;
}
};
```