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
    }
}