Knuth–Morris–Pratt algorithm: Difference between revisions

Content deleted Content added
Line 137:
===Description of pseudocode for the search algorithm===
<!--Note to future editors: please do not replace or even supplement the pseudocode with language-specific code. Following the WikiProject Computer Science manual of style, pseudocode is preferred over real code unless the real code illustrates a feature of the language or an implementation detail. This algorithm is so simple that neither of these can ever be the case-->
The above example contains all the elements of the algorithm. For the moment, we assume the existence of a "partial match" table <code>T</code>, described [[#"Partial match" table (also known as "failure function")|below]], which indicates where we need to look for the start of a new match inwhen thea eventmismatch thatis the current one ends in a mismatchfound. The entries of <code>T</code> are constructed so that if we have a match starting at <code>S[m]</code> that fails when comparing <code>S[m + i]</code> to <code>W[i]</code>, then the next possible match will start at index <code>m + i - T[i]</code> in <code>S</code> (that is, <code>T[i]</code> is the amount of "backtracking" we need to do after a mismatch). This has two implications: first, <code>T[0] = -1</code>, which indicates that if <code>W[0]</code> is a mismatch, we cannot backtrack and must simply check the next character; and second, although the next possible match will ''begin'' at index <code>m + i - T[i]</code>, as in the example above, we need not actually check any of the <code>T[i]</code> characters after that, so that we continue searching from <code>W[T[i]]</code>. The following is a sample [[pseudocode]] implementation of the KMP search algorithm.
 
Line 169:
'''let''' j ← j + 1
'''let''' k ← k + 1
 
 
===Efficiency of the search algorithm===