Implement strStr()

唉 终于到了要记算法的时候了 KMP。。。还没写完 回去再写。。。
。。。
首先可以看这篇文章
http://www.programfan.com/blog/article.asp?id=15762
然后之前代码完全写错了，我觉得KMP的理解和记忆的核心在于两点：1、KMP中next数组的目的在于知道某个字母失配之后应该怎么根据模式串已匹配的字符找最近的最大匹配 2、next数组的生成过程和最后的模式匹配过程基本类似

public class Solution {
    public String strStr(String haystack, String needle) {
        // Start typing your Java solution below
        // DO NOT write main() function
        int lenh = haystack.length();
        int lenn = needle.length();
        if (lenn == 0)
            return haystack;
        int[] next = getNext(needle, lenn);
        int h = 0;
        int n = 0;
        while (h < lenh){
            if (n == 0 || haystack.charAt(h) == needle.charAt(n)){
                if (haystack.charAt(h) == needle.charAt(n)){
                    n++;
                    if (n >= lenn)
                        return haystack.substring(h+1-lenn, lenh);
                }
                h++;
            } else 
                n = next[n];
        }
        return null;
    }
    
    int[] getNext(String needle, int length){
        int[] next = new int[length+1];
        next[0] = 0;
        int pos = 0;
        int des = 1;
        while (des < length){
            if (pos == 0 || needle.charAt(des) == needle.charAt(pos)){
                if (needle.charAt(des) == needle.charAt(pos))
                    pos++;
                des++;
                next[des] = pos;
            } else
                pos = next[pos];
        }
        return next;
    }
}

唉 还是看看上面提到的那个帖子里面的代码吧 比我简单且高效