Knuth–Morris–Pratt algorithm: Difference between revisions

Content deleted Content added
Efficiency of the table-building algorithm: The complexity analysis doesn't consider the inner while loop, which makes the analysis useless. Removed until this problem is resolved.
Line 426:
'''let''' T[pos] ← cnd (only need when all word occurrences searched)
 
===Efficiency of the table-building algorithm===
The complexity of the table algorithm is <code>O(k)</code>, where <code>k</code> is the length of <code>W</code>. This is easy to prove, <code>pos</code> is initialized as 1, and the loop condition is <code>pos < k</code>. <code>pos</code> is increased by 1 every iteration of the loop, thus the loop will take <code>k - 1</code> iterations, which corresponds to an algorithmic efficiency of <code>O(k)</code> using the [[Big O notation]].
 
==Efficiency of the KMP algorithm==