实现 strStr() 函数。

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。

输入: haystack = "hello", needle = "ll"
输出: 2

解析:字符串匹配问题

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

        }
    void getNext(String a,int[] next){
        int len=a.length();
        next[0]=-1;
        int k=-1;
        int j=0;
        while(j < len-1){
            if(k==-1 || a.charAt(k)==a.charAt(j)){//如果前缀的k以及后置的j相等的话，可以确定next[j+1]的值
                k++;
                j++;
                next[j]=k;
            }else{//否则k往前找一个尽可能大的
                k = next[k];
            }
        }

    }
}