Why is the normal case complexity of KMP O(N)?
<p>after finally having understand the KMP-algorithm, its complexity remains unclear. 
For the length of the pattern M and for the length of the text N, I know, in worst case it's O(N+M) (still can't explain, why), but why is it O(N) in the average case?
Thank you in advance for help.</p>