# Using KMP's LPS (longest-prefix-suffix) computation to solve in linear O(N) time

• ``````class Solution {
private:

// the straightforward solution is in O(N^2); using KMP's preprocessing algorithm,
// we can reduce this to O(N)
int longest_palindrome_prefix(const string &s) const
{
/**
* The LPS computation can determine, at any given index i in a string S, the maximum suffix length that
* make up a suffix equal to the prefix. For example: S = "acexxxaceyyy": at S[6], S[7], and S[8] will be
* marked with "1", "2", and "3" respectively because "a", "ac", and "ace" at this points in the string
* make up substrings whose suffixes equal to the string's prefix. This computation can be done in one
* linear scan of the string in O(N) time, using a secondary integer array in O(N) space.
*
* For our purpose in finding the longest palindrome prefix of a string, the idea is simple:
* if we reverse the string, then appending it to the original string (after a special marker),
* the palindromic prefix will show up at the end of the compound string! If we then apply the above algorithm,
* by the end of the linear scan, we'll have a number that correspond to the maximum suffix length of
* the entire compound string, which correspond to a suffix = prefix. And since a palindromic prefix, when
* reversed and appended, will show up as the suffix, we will conveniently have computed the maximum
* length of the palindromic prefix!
*
* For example: consider the string S = "abbaaax". The longest palindrome prefix is "abba".
* 1. Create S' = "abbaaax#xaaabba"
* 2. Compute LPS: lps[] = { 0,  0,  0,  1,  1,  1,  0,  0,  0,  1,  1,  1,  2,  3,  4 }
*            from  S'[] = {'a','b','b','a','a','a','x','#','x','a','a','a','b','b','a'}
* 3. The last element of LPS, 4, is our longest palindrome prefix length!
*/
string kmprev = s;
std::reverse(kmprev.begin(), kmprev.end());
string kmp = s + "#" + kmprev;

vector<int> lps(kmp.size(), 0);   // lps[i] = longest suffix length for substring kmp[0..i] where the suffix == prefix
for (int i = 1; i < (int)lps.size(); ++i)
{
int prev_idx = lps[i - 1];

while (prev_idx > 0 && kmp[i] != kmp[prev_idx])
{
prev_idx = lps[prev_idx - 1];
}

lps[i] = prev_idx + (kmp[i] == kmp[prev_idx] ? 1 : 0);
}

// after KMP's LPS preprocessing, the last index of the LPS array will contain the longest palindrome prefix' length!
return lps[lps.size() - 1];
}

public:

string shortestPalindrome(const string &s)
{
//
// The idea is simple: find the longest palindrome that prefixes the string S.
// The shortest palindrome we can make is by reversing the rest of the string S, and then
// prepending it to the string.
//
// The trick is finding that longest palindrome prefix in an efficient manner.
//
if (s.size() <= 1)
{
return string(s);
}

int k = longest_palindrome_prefix(s);

string the_rest = s.substr(k);
std::reverse(the_rest.begin(), the_rest.end());

return the_rest + s;
}

};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.