Java KMP


  • 0
    J
      public int strStr(String haystack, String needle) {
    	//KMP algorithms
    	if(needle.equals("")) return 0;
    	if(haystack.equals("")) return -1;
    	char[] arr = needle.toCharArray();
    	int[] next = makeNext(arr);
    
    	int i = 0, j = 0; 
    	while (i < haystack.length()) {
    	    while (j >= 0 && haystack.charAt(i) != arr[j]) j = next[j];
    	    i++;
    	    j++;
    	    if (j == needle.length()) return i - j;
    	}
        return -1;
      }
    
      private int[] makeNext(char[] arr){
    	int len = arr.length;
    	int[] next = new int[len + 1];
    
    	next[0] = -1;
    	int i = 0, j = -1;
    	while (i < len) {
    	    while (j >= 0 && arr[i] != arr[j]) j = next[j];
    	    i++;
    	    j++;
    	    next[i] = j;
    	}
    	return next;
      }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.