Knuth–Morris–Pratt algorithm: Difference between revisions

Revision as of 04:52, 10 November 2020

Revision as of 14:44, 8 January 2021

Line 400:

===Description of pseudocode for the table-building algorithm===

<!--Note to future editors: please do not replace or even supplement the pseudocode with language-specific code. Following the WikiProject Computer SscienceScience 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-->

<!--This code appears to implement the table for the Morris-Pratt algorithm, not for the Knuth-Morris-Pratt Algorithm. The KMP table has bigger shifts. See http://www-igm.univ-mlv.fr/~lecroq/string/node8.html-->

The example above illustrates the general technique for assembling the table with a minimum of fuss. The principle is that of the overall search: most of the work was already done in getting to the current position, so very little needs to be done in leaving it. The only minor complication is that the logic which is correct late in the string erroneously gives non-proper substrings at the beginning. This necessitates some initialization code.

Line 421:

'''else'''

'''let''' T[pos] ← cnd

'''let''' cnd ← T[cnd] (to increase performance)

'''while''' cnd ≥ 0 '''and''' W[pos] ≠ W[cnd] '''do'''

'''let''' cnd ← T[cnd]