# A 130ms O(n*k) solution using KMP

• well, we may observe that for example:
s = "catacb"
we want to add "b" to its left.
Should I find the max palindrome start from left 0? Yes.

What if
s = "cacacb"?
we want to add "b" to its left.
we also want to try to add "bca" to it.
That means not only we need find max plindrome start from 0, but also any palindrome which is shorter but exist.

There is a solution in https://leetcode.com/discuss/64309/clean-kmp-solution-with-super-detailed-explanation, which solves how to find max palindrome start from 0. The explanation is great. Thanks for hpplayer's work. So I reckon that maybe I can continue to find any sub palindrome from the existing KMP searching solutions.

The fact is, for example, you solve "cacacb" by solve "cacacb#bcacac" KMP table, you get:
array p = 0,0,1,2,3,0,0,0,1,2,3,4,5
p[last element] = 5 is the max palindrome length start from index 0 of "cacacb", which is "cacac"
p[5 - 1] = 3 is the next sub palindrome length start from index 0 of "cacacb", which is "cac"

What's more, you need to also try to put strings to the right of string:
cacab +> acac
which means you need to also solve the extended string reversely and find and palindrome that ends at last element of the string.

Apology for my messy explanation. Have to run for lab work....

``````public class Solution {
private int[] calKMP(String s) {  //return KMP prefix table
int len = s.length();
int[] p = new int[len];
for (int i = 1; i < len; i++) {
int j = p[i - 1];
while (j > 0 && s.charAt(j) != s.charAt(i)) j = p[j - 1];
p[i] = s.charAt(j) == s.charAt(i) ? j + 1 : j;
}
return p;
}

private void addTo(List<List<Integer>> ansList, int i, String sAdd, boolean toLeft, boolean[][] has, HashMap<String, Integer> h) {
if (toLeft) { //put string index j to the left of i
if (has[j][i]) return; // avoid repeating
ArrayList<Integer> aSolution = new ArrayList<Integer>();
has[j][i] = true;
} else { // put j to the right of i
if (has[i][j]) return; // avoid repeating
ArrayList<Integer> aSolution = new ArrayList<Integer>();
has[i][j] = true;
}
}

public List<List<Integer>> palindromePairs(String[] words) {
boolean toLeft = true;
int n = words.length;
List<List<Integer>> ansList = new ArrayList<List<Integer>>();
HashMap<String, Integer> h = new HashMap<String, Integer>();
boolean[][] has = new boolean[n][n];
for (int i = 0; i < n; i++) {
h.put(words[i], i);
has[i][i] = true;
}

for (int i = 0; i < n; i++) {
int len = words[i].length();
if (len == 0) continue;
String sRev = new StringBuffer(words[i]).reverse().toString();
addTo(ansList, i, sRev, toLeft, has, h);
addTo(ansList, i, sRev, !toLeft, has, h);
addTo(ansList, i, sRev.substring(0, len - 1), toLeft, has, h);
addTo(ansList, i, sRev.substring(1), !toLeft, has, h);

String sP = words[i] + '#' + sRev, sQ = sRev + '#' + words[i];
int[] p = calKMP(sP), q = calKMP(sQ);
int lenExt = 2 * len + 1, j = p[lenExt - 1];
//System.out.println("<" + words[i] + ">'s <" + sP + "> KMP table:");
//for (int k = 0; k < lenExt; k++) System.out.print(p[k] + ","); System.out.println(".");
while (j > 1) {
addTo(ansList, i, sRev.substring(0, len - j), toLeft, has, h);
//System.out.println("try add to ans list: " + sRev.substring(0, len - j) + "<+" + words[i]);
j = p[j - 1];
}
//System.out.println("<" + words[i] + ">'s <" + sQ + "> KMP table:");
//for (int k = 0; k < lenExt; k++) System.out.print(q[k] + ","); System.out.println(".");
j = q[lenExt - 1];
while (j > 1) {
addTo(ansList, i, sRev.substring(j), !toLeft, has, h);
//System.out.println("try add to ans list: " + words[i] + "+>" + sRev.substring(j));
j = q[j - 1];
}
}
return ansList;
}
``````

}

I also print to you the working internal output during the process. Hope you would get a clue:

``````Your input

["abcd", "dcba", "lls", "s", "sssll", "catacb", "catacatacb", "cacacb"]

<abcd>'s <abcd#dcba> KMP table:
0,0,0,0,0,0,0,0,1,.
<abcd>'s <dcba#abcd> KMP table:
0,0,0,0,0,0,0,0,1,.
<dcba>'s <dcba#abcd> KMP table:
0,0,0,0,0,0,0,0,1,.
<dcba>'s <abcd#dcba> KMP table:
0,0,0,0,0,0,0,0,1,.
<lls>'s <lls#sll> KMP table:
0,1,0,0,0,1,2,.
try add to ans list: s<+lls
<lls>'s <sll#lls> KMP table:
0,0,0,0,0,0,1,.
<s>'s <s#s> KMP table:
0,0,1,.
<s>'s <s#s> KMP table:
0,0,1,.
<sssll>'s <sssll#llsss> KMP table:
0,1,2,0,0,0,0,0,1,2,3,.
try add to ans list: ll<+sssll
try add to ans list: lls<+sssll
<sssll>'s <llsss#sssll> KMP table:
0,1,0,0,0,0,0,0,0,1,2,.
try add to ans list: sssll+>sss
<catacb>'s <catacb#bcatac> KMP table:
0,0,0,0,1,0,0,0,1,2,3,4,5,.
try add to ans list: b<+catacb
<catacb>'s <bcatac#catacb> KMP table:
0,0,0,0,0,0,0,0,0,0,0,0,1,.
<catacatacb>'s <catacatacb#bcatacatac> KMP table:
0,0,0,0,1,2,3,4,5,0,0,0,1,2,3,4,5,6,7,8,9,.
try add to ans list: b<+catacatacb
try add to ans list: bcata<+catacatacb
<catacatacb>'s <bcatacatac#catacatacb> KMP table:
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,.
<cacacb>'s <cacacb#bcacac> KMP table:
0,0,1,2,3,0,0,0,1,2,3,4,5,.
try add to ans list: b<+cacacb
try add to ans list: bca<+cacacb
<cacacb>'s <bcacac#cacacb> KMP table:
0,0,0,0,0,0,0,0,0,0,0,0,1,.