My Java KMP Solutions


  • 0
    public class Solution {
        public int strStr(String haystack, String needle) {
    		int len1 = haystack.length();
    		int len2 = needle.length();
    		if (len2 == 0)
    			return 0;
    		if(len1 < len2)
    		    return -1;
    		int[] next = new int[len2];
    		char[] substr = needle.toCharArray();
    		char[] str = haystack.toCharArray();
    		getNext(substr, next);
    		int i = 0, j = 0;
    		while (i < len1 && j < len2) {
    			if (j == -1 || str[i] == substr[j]) {
    				++i;
    				++j;
    			} else {
    				j = next[j];
    			}
    		}
    		if (len2 == j)
    			return i - j;
    		return -1;
    	}
    
    	private void getNext(char str[], int next[]) {
    		int i = 0, j = -1;
    		next[0] = -1;
    		int len = str.length;
    		while (i < len - 1) {
    			if (j == -1 || str[i] == str[j]) {
    			    ++i;
    				++j;
    				if (str[i] == str[j])
    					next[i] = next[j];
    				else
    					next[i] = j;
    
    			} else
    				j = next[j];
    		}
    	}
    }

  • 0
    O

    A sincere engineer


Log in to reply
 

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