Shortest Palindrome — KMP on Reversed String

Problem (LeetCode 214)

Given string s, find the shortest palindrome by adding characters only at the front.

Example: s = "abcd" → "dcbabcd" (add "dcb" to front)

Key Insight — KMP on s + '#' + reverse(s)

The longest prefix of s that is also a palindrome = longest proper prefix-suffix of s + '#' + rev(s).

s = "abacaba"
combined = "abacaba#abacaba"
KMP LPS at last position = 7 → entire s is palindrome → answer = s

Solutions

Python

def shortestPalindrome(s):
    rev = s[::-1]
    combined = s + '#' + rev
    n = len(combined)
    lps = [0]*n
    length = 0
    i = 1
    while i < n:
        if combined[i] == combined[length]:
            length += 1
            lps[i] = length
            i += 1
        elif length:
            length = lps[length-1]
        else:
            lps[i] = 0
            i += 1
    return rev[:len(s)-lps[-1]] + s

JavaScript

function shortestPalindrome(s){
    const rev=[...s].reverse().join(''),comb=s+'#'+rev,n=comb.length;
    const lps=new Array(n).fill(0); let len=0,i=1;
    while(i<n){if(comb[i]===comb[len])lps[i++]=++len;else if(len)len=lps[len-1];else lps[i++]=0;}
    return rev.slice(0,s.length-lps[n-1])+s;
}

Java

public String shortestPalindrome(String s){
    String rev=new StringBuilder(s).reverse().toString();
    String comb=s+'#'+rev; int n=comb.length();
    int[]lps=new int[n]; int len=0,i=1;
    while(i<n){if(comb.charAt(i)==comb.charAt(len))lps[i++]=++len;else if(len>0)len=lps[len-1];else lps[i++]=0;}
    return rev.substring(0,s.length()-lps[n-1])+s;
}

C++

#include <string>
#include <algorithm>
using namespace std;
string shortestPalindrome(string s){
    string rev(s.rbegin(),s.rend()), comb=s+'#'+rev; int n=comb.size();
    vector<int>lps(n,0); int len=0,i=1;
    while(i<n){if(comb[i]==comb[len])lps[i++]=++len;else if(len)len=lps[len-1];else lps[i++]=0;}
    return rev.substr(0,s.size()-lps[n-1])+s;
}

C

/* C: same KMP on concatenated string */