Knuth–Morris–Pratt algorithm: Difference between revisions

Revision as of 19:55, 5 August 2020

Revision as of 15:59, 6 August 2020

Line 433:

* The outer loop: <code>pos</code> is initialized to 1, the loop condition is <code>pos < k</code>, and <code>pos</code> is increased by 1 in every iteration of the loop. Thus the loop will take <math>k - 1</math> iterations.

* The inner loop: <code>T[cnd]</code> is alwaysinitialized less thanto <code>cnd0</code>, so <code>cnd</code>and gets decreasedincreased by at leastmost 1 in each outer loop iteration. <code>T[cnd]</code> is initializedalways toless than <code>0cnd</code>, andso <code>cnd</code> gets increaseddecreased by at mostleast 1 in each outerinner loop iteration; the inner loop condition is <code>cnd ≥ 0</code>. This means that the inner loop can execute at most as many times in total, as the outer loop has executed – each decrease of <code>cnd</code> by 1 in the inner loop needs to have a corresponding increase by 1 in the outer loop. Since the innerouter loop takes <math>k - 1</math> iterations, the inner loop can take no more than <math>k - 1</math> iterations in total.

Combined, the outer and inner loops take at most <math>2k-2</math> iterations. This corresponds to <math>O(k)</math> time complexity using the [[Big O notation]].