28. Implement strStr()

public class Solution {
    public int strStr(String haystack, String needle) {
        int[] next=new int[needle.length()];
        generateNextArray(next,needle);
        int i=0;
        int j=0;
        while(i<haystack.length()&&j<needle.length())
        {
            if(j==-1||haystack.charAt(i)==needle.charAt(j))
            {
                i++;
                j++;
            }
            else
                j=next[j];
        }
        if(j==needle.length())
            return i-j;
        return -1;
    }
    void generateNextArray(int[] next, String needle)
    {
        int k=-1;
        if(next.length>0)
            next[0]=-1;
        int i=0;
        while(i<needle.length()-1)
        {
            if(k==-1||needle.charAt(k)==needle.charAt(i))
            {
                k++;
                i++;
                next[i]=k;
            }
            else
                k=next[k];
        }
    }
}

 http://blog.csdn.net/v_july_v/article/details/7041827