leetcode28 實作 strStr() KMP算法

KMP算法主要應用于字元串比對上。當出現字元串不比對時，可以知道之前已經比對的文本内容，利用此部分資訊避免從頭比對

//KMP算法
       public int strStr(String haystack, String needle) {
        if (needle.isEmpty()) return 0;
        int h=haystack.length();int n=needle.length();

        char[] crrh=haystack.toCharArray();
        char[] crrn=needle.toCharArray();

        int[] next=new int[n];//字首表
        next[0]=0;
//構造next數組
        for(int i=1,j=0;i<n;){
           if(crrn[i]==crrn[j])
           {
               //如果相等，next[i]=j+1;i++;j++
               next[i++]=++j;
               //i++;
               //j++;
           }else {
               //如果不相等,j=next[j-1],直到j==0,next[i]=0;i++
               if(j==0) next[i++]=0;
               else {j=next[j-1];}
           }

        }
        //開始進行比對
        for(int i=0,j=0;i<h;){
            if (crrh[i]==crrn[j]){
                //如果比對成功
                i++;j++;
            }else{
                //如果某位置不比對，去前面比對的位置，尋找最大相同字首字尾
                //它們的字首相同，是以不需要重新比對
                //如果還是不同，就重頭開始
               if(j>0) j=next[j-1];
                else i++;
            }
            if (j==n) return i-n;
        }
        return -1;
    }