Knuth Morris Prat or KMP algorithm is one of the pattern matching algorithms, that helps find if a given pattern p is present in the given String s.
The time complexity of pattern matching is O(m+n) where m is the length of the pattern and n is the length of the given string
class Solution {
public int strStr(String haystack, String needle) {
int n = haystack.length();
int m = needle.length();
if(m > n) return -1; // if the needle length is more than the haystack length
if(m ==0) return 0;// if the needle length if 0
//using Knuth Morris Pratt pattern matching algorithm
//tc : O(n+m)
//for understanding what KMP algo is refer this: https://www.youtube.com/watch?v=GTJr8OvyEVQ
//step1: build fallback array by creating the pattern prefix and suffix match( for more details on this refer the link give above )
int fallback[] = new int[m];
int i = 0,j=i+1;
while(i<m && j<m){
if(needle.charAt(i) == needle.charAt(j)){
fallback[j] = i+1;
i++;j++;
}
else{
if(i>0) i = fallback[i-1];
else fallback[j++] = 0;
}
}
// step2: use the fallback array for to search the needle in the haystack
i=0;
j=0;
while(i<n && j<m){
if(haystack.charAt(i) == needle.charAt(j)) {i++;j++; }
else {
if(j>0) j = fallback[j-1];
else i++;
}
}
return j == m ? i-j : -1; // j =m means we have found the needle at index i-j in the haystack
}
}
Top comments (0)