# 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