# Why is KMP preprocessing O(N)?

My intuition tells me that there is <=1 increase in lps for each increase in the index. Can someone make a better argument why this is O(N)? My confusion arises from len_ = lps[len_- 1] .

def computeLPSArray(pat, M, lps):
len_ = 0 # length of the previous longest prefix suffix

lps[0] = 0 # lps[0] is always 0
i = 1

# the loop calculates lps[i] for i = 1 to M-1

while i < M:
if pat[i]== pat[len_]:
len_ += 1
lps[i] = len_
i += 1
else:
# This is tricky. Consider the example.
# AAACAAAA and i = 7. The idea is similar
# to search step.
if len_ != 0:
len_ = lps[len_- 1]

# Also, note that we do not increment i here
else:
lps[i] = 0
i += 1

$$$$


Each len_ = lps[len - 1] decreases $$lps$$ by at least 1, thus, it can only happen for lps[i - 1] + 1 - lps[i] times, since you initialize lps[i] as lps[i - 1] + 1. Therefore, the maximum number of times len_ = lps[len - 1]` can happen is $$\displaystyle \sum_{i=1}^n (lps[i - 1] + 1) - lps[i]$$. As you know, $$lps$$ can increase by at most $$n$$ in total, therefore, it can decrease by at most $$n$$ in total, since $$lps$$ can never be negative, or equivalently, for each $$+1$$ $$lps$$ gets, it can get at most one $$-1$$. thus $$\displaystyle \sum_{i=1}^n (lps[i - 1] + 1) - lps[i]$$ will be $$O(n)$$.