Iam_Sandeep

KMP pattern search algorithm

Dec 9th, 2021
578
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. https://leetcode.com/problems/implement-strstr/submissions/
  2.  
  3. class Solution:
  4.     def strStr(self, haystack: str, needle: str) -> int:
  5.         if needle=="":return 0
  6.         m,l,r,n=len(needle),0,1,len(haystack)
  7.         lps=[0]*m#left prefix sum
  8.         """
  9.        l,r:two pointers
  10.        """
  11.         while r<m:#creating lps of needle
  12.             if needle[l]==needle[r]:
  13.                 lps[r]=l+1
  14.                 l,r=l+1,r+1
  15.             else: #if vals are not same
  16.                 if l==0:#base case to get rid of left moving index and inc r pointer
  17.                     lps[r]=0
  18.                     r+=1
  19.                 else:
  20.                     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].
  21.                    
  22.         """
  23.        np:needle pointer
  24.        hp:haystack pointer
  25.        """
  26.         np,hp=0,0
  27.         while hp<n:
  28.             if needle[np]==haystack[hp]:
  29.                 np,hp=np+1,hp+1
  30.             else:
  31.                 if np==0:#if we cant move np left move rp up
  32.                     hp+=1
  33.                 else:
  34.                     np=lps[np-1]#same logic of lps used above
  35.                    
  36.             if np==m:#we found the pattern or search
  37.                 return hp-m #index of start of target
  38.        
  39.         return -1 #we couldnt find any target
  40.        
  41.            
  42.        
  43.        
  44.    
  45.        
RAW Paste Data