/*
* Return the index of the first occurrence of needle in haystack,or -1 if needle is not part
of haystack.Clarification:
What should we return when needle is an empty string?This is a great question to ast during
an interview.
For the purpose of this problem,we will return 0 when needle is an empty string.This is consistent
to C'S strStr() and Java's indexOf().

* Example 1:

Input:haystack="hello",needle="ll"
Output:2
*
Example 2:
Input:haystack ="aaaaa",needle="bba"
Output: -1

* 题目解释:
* 其实这道题很容易理解,但需要注意模式串为0时,应该返回0;模式串长度大于主串长度时,应该返回-1.
* 方法1:
* 暴力破解
* 方法2:
* KMP算法

public class ImplementstrStr {
    public int strStr(String haystack,String needle){
        int haylen=haystack.length();
        int needlen=needle.length();
        if(haylen<needlen)
            return -1;
        if(needlen==0)
            return 0;
        /*主串*/
        for(int i=0;i<haylen-needlen+1;i++){
            int j;
            /*模式串*/
            for(j=0;j<needlen;j++){
                if(haystack.charAt(i+j)!=needle.charAt(j))
                    break;/*不符合的情况,直接跳出,主串指针后移一位*/
            }
            /*匹配成功*/
            if(j==needlen){
                return i;
            }
        }
        return -1;
    }
    public  int strStr1(String haystack,String needle){
        /*两种特殊情况*/
        if(needle.length()==0)
            return 0;
        if(haystack.length()==0)
            return -1;
        /*字符char数组*/
        char[] hasyarr=haystack.toCharArray();
        char[] nearr=needle.toCharArray();

        int halen=hasyarr.length,nelen=nearr.length;
        /*返回下标*/
        return kmp(hasyarr,halen,nearr,nelen);
    }
    private int kmp(char[] hasyarr,int halen,char[] nearr,int nelen){
        /*获取next数组*/
        int[] next=next(nearr,nelen);
        int j=0;
        for(int i=0;i<halen;i++){
            /*发现不匹配的字符,然后根据next数组移动指针,移动到最大公共前后缀*/
            while(j>0&&hasyarr[i]!=nearr[j]){
                j=next[j-1]+1;
                /*超出长度时,可以直接返回不存在*/
                if(nelen-j+i>halen){
                    return -1;
                }
            }
            /*如果相同就将指针同时后移动一位*/
            if(hasyarr[i]==nearr[j]){
                j++;
            }
            /*遍历完整个模式串*/
            if(j==nelen){
                return i-nelen+1;
            }
        }
        return -1;
    }
    private int[] next(char[] needle,int len){
        /*定义next数组*/
        int[] next=new int[len];
        next[0]=-1;
        int k=-1;
        /*遍历求最长前后缀,next[k]记录子串最长公共前后缀的尾坐标,即长度*/
        for(int i=1;i<len;i++){
            /*找k+1前一个元素在next数组里的值,即next[k+1]*/
            while(k!=-1&&needle[k+1]!=needle[i]){
                k=next[k];
            }
            /*相同情况下,就是k的下一位,和i相同时,此时已经知道[0,i-1]的最长前后缀,
            * 然后k-1和i相同,最长前后缀加1*/
            if(needle[k+1]==needle[i]){
                k++;
            }
            next[i]=k;
        }
        return next;
    }

    public static void main(String[] args){
        String haystack="hello",needle="ll";
        ImplementstrStr str=new ImplementstrStr();
        System.out.println(str.strStr1(haystack,needle));
    }
}