KMP pattern search algorithm

https://leetcode.com/problems/implement-strstr/submissions/
'''
LPS stands for longest proper prefix suffix.
Proper prefix means prefix which is not same as original string.
Same for proper suffix.
'''
class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if needle=="":return 0
        m,l,r,n=len(needle),0,1,len(haystack)
        lps=[0]*m#left prefix sum
        """
        l,r:two pointers
        """
        while r<m:#creating lps of needle
            if needle[l]==needle[r]:
                lps[r]=l+1
                l,r=l+1,r+1
            else: #if vals are not same
                if l==0:#base case to get rid of left moving index and inc r pointer
                    lps[r]=0
                    r+=1
                else:
                    l=lps[l-1]# till l-1 we had the prefix and suffix of size lps[l-1]. So start again search from lps[l-1].

        """
        np:needle pointer
        hp:haystack pointer
        """
        np,hp=0,0
        while hp<n:
            if needle[np]==haystack[hp]:
                np,hp=np+1,hp+1
            else:
                if np==0:#if we cant move np left move rp up
                    hp+=1
                else:
                    np=lps[np-1]#same logic of lps used above

            if np==m:#we found the pattern or search
                return hp-m #index of start of target

        return -1 #we couldnt find any target