[Java] Knuth–Morris–Pratt text search algorithm

The Knuth–Morris–Pratt algorithm is an efficient way of searching for a pattern within some text. By precomputing prefix information from the pattern using extra O(M) space, it gives a O(N+M) algorithm that finds all occurrences of a given string within another string.

The idea is that if some portions of the pattern repeat AND we had found a match until a certain point in the pattern, we do not need to go all the way back to the start of the text, but can continue with an offset that is equal to the matched portion.

You can check my implementation of searchSubstringKMP on my Gist along with some tests in KMPJTests.