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 # lps 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 ```