KMP

   public int strStr(String haystack, String needle) {
    if(needle == null ||needle.length()==0)return 0;
    if(haystack == null ||haystack.length()==0)return -1;
    int[] next = makeInt(needle);
    int j=0;
    int i=0;
    while(j<needle.length()&&i<haystack.length()){
        if(j==-1 || haystack.charAt(i)==needle.charAt(j)){
            i++;
            j++;
            if(j==needle.length())return i-j;
        }else {
            j = next[j];
        }
    }
    
    if(j==needle.length())return i-j;
    return -1;
}
private int[] makeInt(String needle){
    int[] next = new int[needle.length()+1];
    next[0]=-1;
    int j=-1;
    int i=0;
    while(i<needle.length()){
        if(j==-1 || needle.charAt(i)==needle.charAt(j)){
            i++;
            j++;
            next[i]=j;
        }else {
            j = next[j];
        }
    }
    return next;
}