Java KMP preprocess O(n)

  • 2
    //S is the pattern to be preprocessed
    //output[i] is the failure index that output redirected to
    public static int[] KMPpreprocess(String S){
    	int[] pi=new int[S.length()];
    	//init start of pi
    	//get each index in pi, i is the index being processed
    	for (int i=1;i<pi.length;i++){
    		int j=pi[i-1];
    		while (j!=-1 && S.charAt(j+1)!=S.charAt(i)) {j=pi[j];}
    		if (j==-1){
    			if (S.charAt(0)==S.charAt(i)) pi[i]=0;
    			else pi[i]=-1;
    		else if (S.charAt(j+1)==S.charAt(i)){
    	return pi;
    public static String reverse(String s){
    	char[] outC=new char[s.length()];
    	for (int i=0;i<outC.length;i++){
    	return new String(outC);
    public static String shortestPalindrome(String s) {
        String sPlus=s+"#"+reverse(s);
        int[] PI=KMPpreprocess(sPlus);
        int palinIndex=Math.min(PI[PI.length-1],s.length()-1);
        String nonPalin=s.substring(palinIndex+1);
        String Palin=s.substring(0,palinIndex+1);
        return reverse(nonPalin)+Palin+nonPalin;

Log in to reply

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