2
$\begingroup$

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

```
$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.