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 1970 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 word being searched, i.e. S[m] =? W. If a match is found, the algorithm tests the other characters in the word being searched by checking successive values of the word position index, i. The algorithm retrieves the character W[i] in the word being searched 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...

Tags
graph, knuth, match, matching, minimum spanning tree, morris, pattern, pratt, searching, string

Implementations