Why is KMP preprocessing O(N)? My intuition tells me that there is &lt;=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 &lt; 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)$.
I hope my answer was helpful.