KMP algorithm O(M+N)


  • 0
    I

    I use the KMP algorithm instead the brute-force, so the time complexity is O(M+N) instead of O(MN), but it seems like it take more time for a smaller input size

    code is below:

     public int strStr(String source, String pattern) {
    
    	int[] pttn = this.next(pattern);
    
    	if (pttn == null || source == null || source.length() == 0
    			|| source.length() < pattern.length()) {
    		return -1;
    	}
    
    	int sn = source.length();
    	int pn = pattern.length();
    	int i = 0;
    	int j = 0;
    	while (i+j <sn) {
    		
    		if (source.charAt(i+j) == pattern.charAt(j)) {
    			if (j == pn - 1)
    				return i;
    			j++;
    		} else {
    			if (j != 0) {
    				// find the initial i 
    				i = i + j - pttn[j - 1];
    				j = 0;
    			} else {
    				i++;
    				j = 0;
    			}
    		}
    
    	}
    
    	return -1;
    
    }
    
    
    
    
    
    private int[] next(String pattern) {
    
    	if (pattern == null || pattern.length() == 0) {
    		return null;
    	}
    
    	int len = pattern.length();
    	int[] result = new int[len]; // 建立匹配表
    	result[0] = 0;
    
    	int i = 1; // pattern 指针
    	int j = 0; // 最大匹配长度, pattern 上的最大匹配长度
    
    	while (i < len) {
    
    		if (pattern.charAt(j) == pattern.charAt(i)) {
    			// 如果匹配 则 j+1, 然后assign给相对应的匹配表
    			j++;
    			result[i] = j;
    			i++;
    		} else {
    			// 如果不匹配-则j 开始回退
    
    			if (j != 0) {
    				// 当j不为0时, j 退1(前一位 和 i-1 时候 有匹配), 查表找出对应的匹配表值, j 退到当前位置
    				j = result[j - 1];
    			} else {
    				// 当j为0时, 说明已经没有任何值与 pattern[i] 匹配, 所以匹配长度应该为0, i++
    				// 开始进行下一轮匹配
    				result[i] = j;
    				i++;
    			}
    
    		}
    
    	}
    
    	System.out.println(Arrays.toString(result));
    	return result;
    
    }

Log in to reply
 

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