|
</code>
This time we are able to complete the match, whose first character is <code>S[15]</code>.
===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 in the event that the current one ends in a mismatch. 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.
'''algorithm''' ''kmp_search'':
'''input''':
an array of characters, S (the text to be searched)
an array of characters, W (the word sought)
'''output''':
an integer (the [[Array data type|zero-based]] position in S at which W is found)
'''define variables''':
an integer, m ← 0 (the beginning of the current match in S)
an integer, i ← 0 (the position of the current character in W)
an array of integers, T (the table, computed elsewhere)
'''while''' m + i < length(S) '''do'''
'''if''' W[i] = S[m + i] '''then'''
'''if''' i = length(W) - 1 '''then'''
'''return''' m
'''let''' i ← i + 1
'''else'''
'''if''' T[i] > -1 '''then'''
'''let''' i ← T[i], m ← m + i - T[i]
'''else'''
'''let''' i ← 0, m ← m + 1
(if we reach here, we have searched all of S unsuccessfully)
'''return''' the length of S
===Efficiency of the search algorithm===
| 