[Java] Find word in matrix using KMP pattern searching

Here is an implementation that finds whether a word appears in a matrix, using a more efficient approach based on KMP algorithm for string search.

We can do the word preprocessing in O(S) time, then we walk the matrix and after we have read a whole row or column, we run our algorithm using the whole row or column as our text.

Therefore we do NM work to read all the maximum length strings represented by a whole row or column, giving us a total of N strings of length M + M strings of length N. On each of these we do M and N work respectively to test for a match, giving us total time of O(NM + NM + MN + S) which is O(NM + S) using O(S) extra space.

You can check my implementation of wordSearchLRTBusingKMP on my Gist along with some tests in WordSearchLRTBusingKMPJTests.