KMP pattern search

Checking the pattern at every start of the text compares the same letters again and again: O(n × m). KMP never moves back in the text. After a mismatch it already knows which part of the pattern still matches: the longest prefix of what matched that is also its suffix (LPS). Watch Akshay's LongestPrefixSuffix fill the lps table, then his PatternFinder walk the text once.

target is the text, pattern the letters searched for, with lps under it: lps[i] is the length of the longest proper prefix of pattern[0..i] that is also its suffix. During the search the pattern and its lps slide along under the text, lined up with the letters they are compared with.