【程序员必会十大算法】之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