【程式員必會十大算法】之KMP

推薦學習文章

代碼

public class Main {
    public static void main(String[] args) {
       //
        int i = violenceMatch("我是 我是最 我是最帥的", "我是最帥的");
        System.out.println(Arrays.toString(getNext("aabaaf")));
        System.out.println(KMP(getNext("aabaaf"),"aabaabaaf","aabaaf"));

    }
    //求解next數組
    public static int[] getNext(String s){//s 是傳進來的模式串
        //首先建立next數組
        int[] next = new int[s.length()];
        //将字元串轉化為數組
        char[] chars = s.toCharArray();

        //第一個元素為0
        next[0] = 0;

        //i 是字尾碼的最後一位，j 是字首碼的最後一位
        //比如字尾碼是aaf，那麼i就指向f
        //比如字首碼是aaf，那麼j就指向f
        int j = 0;
        for (int i = 1;i < next.length;i++){//i 從1 開始，因為0已經指派了
            //如果i和j指向的不相等
            //如果不相等，則j要不斷回溯到最終位置（要麼回溯到第一個，要麼回溯到i和j指向的數相等的位置）
            //！！！ 這裡有一個非常易錯的點，就是j要用while循環進行回溯
            //！！！ 還有 就是這個一定要放在最前面，不然下面的if無法做事
            while (j > 0 && chars[i] != chars[j]){
                j = next[j - 1];
            }

            //如果i和j指向的相等
            if (chars[i] == chars[j]){
                j++;
            }
            //然後給next數組指派
            next[i] = j;
        }

        return next;
    }

    //根據next數組進行KMP

    /**
     *
     * @param next next數組
     * @param string1 原字元串
     * @param string2 模式串
     * @return
     */
    public static int KMP(int[] next,String string1,String string2){
        if (string1.length() == 0 || string2.length() == 0){
            return -1;
        }

        //首先得到字元數組
        char[] bigChars = string1.toCharArray();
        char[] smallChars = string2.toCharArray();

        //然後定義模式串的索引j
        int j = 0;
        for (int i = 0;i < bigChars.length;i++){//還是要記住一點，不管是否比對上，i都要++
            //如果i和j指向的不相等,j傳回next數組指向的位置（KMP）的精髓
            //！！！ 這裡有一個非常易錯的點，就是j要用while循環進行回溯
            while (j > 0 && bigChars[i] != smallChars[j]){
                j = next[j - 1];//這裡直接是next[j]的
            }
            //如果i和j指向的字元相等
            if (bigChars[i] == smallChars[j]){
                //i++;  這裡不應該有i++ 因為i++在for循環中有
                j++;
            }
            //循環退出條件（方法傳回條件）
            if (j == smallChars.length){
                //說明比對到最後了，傳回索引位置
                return i - smallChars.length + 1;
            }
        }

        return -1;
    }
    
    //暴力比對
    public static int violenceMatch(String str1,String str2){
        //将字元串轉為字元數組
        char[] str1Array = str1.toCharArray();
        char[] str2Array = str2.toCharArray();

        //定義字元數組的索引
        int str1Index = 0;
        int str2Index = 0;

        while (str1Index < str1Array.length && str2Index < str2Array.length){
            //當比對成功的時候，都++
            if (str1Array[str1Index] == str2Array[str2Index]){
                str1Index++;
                str2Index++;
            }else {
                //比對不成功，包括兩種情況，一是在比對成功之後的失敗，二是一開始就失敗，但都可以用一個公式
                str1Index = str1Index - (str2Index - 1);
                str2Index = 0;
            }
        }

        if (str2Index == str2Array.length){
            //說明找到了
            return str1Index - str2Index;
        }else {
            //沒找到
            return  -1;
        }
    }
}      

[0, 1, 0, 1, 2, 0]
3