KMP算法

KMP为的是解决2字符串匹配问题的算法，检查一个字符串是否为另一个的子串，sub = "abc" , str = "aabcd" ,str里包含了一个sub，KMP算法可以以O(M+N)的复杂度找到子串在str的位置。

那代码怎么实现呢：

public class Kmp {
	
	public static void main(String[] args) {
		 String str = "abbabbbbcab";   
	     String sub = "bbcab"; 
	     char[] s=str.toCharArray();
	     char[] t=sub.toCharArray();
	    System.out.println("s包含t的位置"+KMP_Index(s, t)); 
	}
	
	/**
	 * @param s
	 * @param t
	 * @return 匹配成功 返回模式串在主串中的头下标，匹配失败返回-1  
	 */
	 public static int KMP_Index(char[] s, char[] t) {  
	        int[] next = next(t);  
	        int i = 0;  
	        int j = 0;  
	        while (i <= s.length - 1 && j <= t.length - 1) {  
	            if (j == -1 || s[i] == t[j]) {  
	                i++;  
	                j++;  
	            } else {  
	                j = next[j];  
	            }  
	        } 
	        
	        if (j < t.length) {  
	            return -1;  
	        } else {
	        	return i - t.length; 
	        } 
	    }  
	
	public static int[] next(char[] t) {  
        int[] next = new int[t.length];  
        next[0] = -1;  
        int i = 0;  
        int j = -1;  
        while (i < t.length - 1) {  
            if (j == -1 || t[i] == t[j]) {  
                i++;  
                j++;  
                if (t[i] != t[j]) {  
                    next[i] = j;  
                } else {  
                    next[i] = next[j];  
                }  
            } else {  
                j = next[j];  
            }  
        }  
        return next;  
    }  
	
}