字元串的模式比對（BF算法，KMP算法）

模式比對含義：給定兩個字元串，在主串s中查找子串T的過程就稱為字元串的模式比對。

BF算法：基本思想就是暴力比對，将子串的第一個字元與主串的第一個字元進行比較，若相等，則比較第二個字元。若不相等，則與主串的第二個字元進行比較，以此類推，直到比對到為止。

代碼如下：

//傳回模式串t在主串中從start開始的第一次比對位數
    public int indexOf(SeqString t,int start){
        if (this!=null && t!=null && t.length()>0 && this.length()>t.length()){
            int slen,tlen,i=start,j=0;
            slen=this.length();
            tlen=t.length();
            while (i<slen && j<tlen){
                if (this.charAt(i)==t.charAt(j)){
                    i++;
                    j++;
                }
                else{
                    //繼續比較下一個字串
                    i=i-j+1;
                    j=0;
                }
            }
            if (j>t.length()){
                //比對成功，傳回子串序号
                return i-tlen;
            }
            else{
                return -1;
            }
        }
        return -1;
    }
           

KMP算法是一種改進的字元串比對算法，主要實作方式是主串的x指針不回溯，修改y指針的指向，使其移動到有效的位置，進而大大提高了字元串比對效率。

next指針的作用：當x與y指針指向的字元不同時，讓y指針指向next[y]對應的位置即可。

next數組儲存的就是已比對過子串字首的“最長可比對字首子串”和“最長可比對字尾子串”的最長共有元素的長度。

擷取next數組代碼

public static int[] getNext(String str){
        int[] next=new int[str.length()];
        next[0]=-1;
        //y為索引，len為最長共有元素的長度
        int y=0,len=-1;
        //定義一個循環，用來計算next數組
        while (y<str.length()-1){
            //處理len何y指向模式串中字元相等的情況
            if (len==-1 || str.charAt(len)==str.charAt(y)){
                y++;
               len++;
               next[y]=len;
            }
            //處理len何y指向模式串中字元不相等的情況
            else{
                len=next[len];
            }
        }
        return next;
    }

           

KMP算法代碼

public static int KmpSearch(String str1,String str2){
        int[] next=getNext(str2);
        int x=0,y=0;
        while (x<str1.length()&& y<str2.length()){
            if (y==-1 || str1.charAt(x)==str2.charAt(y)){
                x++;
                y++;
            }
            else{
                y=next[y];
            }
        }
        if (y==str2.length()){
            return x-y;
        }
        return -1;
    }
           

擷取next數組優化算法代碼

public static int[] getNext(String str){
        int[] next=new int[str.length()];
        next[0]=-1;
        //y為索引，len為最長共有元素的長度
        int y=0,len=-1;
        //定義一個循環，用來計算next數組
        while (y<str.length()-1){
            //處理len何y指向模式串中字元相等的情況
            if (len==-1 || str.charAt(len)==str.charAt(y)){
//                y++;
//                len++;
                //如果len和y指向的字元相等  KMP算法優化
                if(str.charAt(++len)==str.charAt(++y)){
                    next[y]=next[len];
                }
                else{
                    next[y]=len;
                }
                next[y]=len;
            }
            //處理len何y指向模式串中字元不相等的情況
            else{
                len=next[len];
            }
        }
        return next;
    }
           

完整代碼如下

//實作KMP算法
    public static int KmpSearch(String str1,String str2){
        int[] next=getNext(str2);
        int x=0,y=0;
        while (x<str1.length()&& y<str2.length()){
            if (y==-1 || str1.charAt(x)==str2.charAt(y)){
                x++;
                y++;
            }
            else{
                y=next[y];
            }
        }
        if (y==str2.length()){
            return x-y;
        }
        return -1;
    }
    //計算next數組
    public static int[] getNext(String str){
        int[] next=new int[str.length()];
        next[0]=-1;
        //y為索引，len為最長共有元素的長度
        int y=0,len=-1;
        //定義一個循環，用來計算next數組
        while (y<str.length()-1){
            //處理len何y指向模式串中字元相等的情況
            if (len==-1 || str.charAt(len)==str.charAt(y)){
//                y++;
//                len++;
                //如果len和y指向的字元相等  KMP算法優化
                if(str.charAt(++len)==str.charAt(++y)){
                    next[y]=next[len];
                }
                else{
                    next[y]=len;
                }
                next[y]=len;
            }
            //處理len何y指向模式串中字元不相等的情況
            else{
                len=next[len];
            }
        }
        return next;
    }