See On Github

Wikipedia Description

In computer science, the KnuthMorrisPratt string searching algorithm (or KMP algorithm ) searches for occurrences of a word W within a main text string S by employing the observation that when a mismatch occurs, the word itself embodies sufficient information to determine where the next match could begin, thus bypassing re-examination of previously matched characters. The algorithm was conceived in 1974 by Donald Knuth and Vaughan Pratt, and independently by James H. Morris. The three published it jointly in 1977. A string matching algorithm wants to find the starting index m in string S[] that matches the search word W[] . The most straightforward algorithm is to look for a character match at successive values of the index m, the position in the string being searched, i.e. S[m]. If the index m reaches the end of the string then there is no match, in which case the search is said to fail. At each position m the algorithm first checks for equality of the first character in the searched for word, i.e. S[m] =? W[0]. If a match is found, the algorithm tests the other characters in the searched for word by checking successive values of the word position index, i. The algorithm retrieves the character W[i] in the searched for word and checks for equality of the expression S[m+i] =? W[i]. If all successive characters match in W at position m, then a match is found at that position in the search string. https://en.wikipedia.org/wiki/Knuth%E2%80%93Morr...

Implementations