KMP算法

逸帅

2、KMP算法

2.1、解决的问题

KMP是一个解决模式串在文本串是否出现过，如果出现过，找出最早出现的位置的经典算法，用来解决暴力匹配算法的不足

2.2、算法思路

2.2.1、部分匹配表的生成

什么是前缀与后缀：

• 前缀：ABCD的前缀为[A, AB, ABC]
• 后缀：ABCD的后缀为[BCD, CD, D]

部分匹配值”就是”前缀”和”后缀”的最长的共有元素的长度。以”ABCDABD”为例，

• ”A”的前缀和后缀都为空集，共有元素的长度为 0；
• ”AB”的前缀为[A]，后缀为[B]，共有元素的长度为 0；
• ”ABC”的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度 0；
• ”ABCD”的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为 0；
• ”ABCDA”的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为”A”，长度为 1；
• ”ABCDAB”的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为”AB”，长度为 2；
• ”ABCDABD”的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD,D]，共有元素的长度为 0。

如下表：

2.2.2、匹配过程

问题：假设有一个字符串 str1= BBC ABCDAB ABCDABCDABDE，和一个子串 str2=ABCDABD。现在要判断 str1 是否含有 str2, 如果存在，就返回第一次出现的位置, 如果没有，则返回-1

步骤：

1. 首先，用 str1的第一个字符和 str2的第一个字符去比较，不符合，关键词向后移动一位

2. 重复第一步，还是不符合，再后移

3. 一直重复，直到 Str1有一个字符与 Str2的第一个字符符合为止

4. 接着比较字符串和搜索词的下一个字符，还是符合

5. 遇到 Str1有一个字符与 Str2对应的字符不符合

6. 这时候不能像暴力匹配一样移动到最前面的下一个字符，因为前面的字符都匹配过了，当空格与 D 不匹配时，你其实知道前面六个字符是”ABCDAB”，这时候不要把”搜索位置”移回最前面的位置，而是根据匹配表，决定移动到哪个位置，这样就节省了效率，匹配表按照2.2.1的方法，进行计算

7. 已知空格与 D 不匹配时，前面六个字符”ABCDAB”是匹配的。查表可知，最后一个匹配字符 B 对应的”部分 匹配值”为 2， 因此按照下面的公式算出向后移动的位数：

   移动位数 = 已匹配的字符数 - 对应的部分匹配值，因为 6 - 2 等于 4， 所以将搜索词向后移动 4 位。

8. 此时C与空格不匹配，已经匹配的是“AB”两个字符，对应的”部分匹配值”为 0。

   所以，移动位数 = 2 - 0， 结果为 2， 于是将搜索词向后移 2 位

9. 继续按照字符，一个一个匹配，A与空格不匹配，后移一位，此时开始匹配

10. 逐位比较，C和D不匹配，此时前面匹配的依然是“ABCDAB”，按照前面第六步的方法，构建匹配表，可知要往后移动4位

11. 逐位匹配，此时发现完全匹配，代表找到了。

2.3、代码实现

package com.yishuai.Algorithm;

import java.util.Arrays;

/**
 * @author yishuai
 * @description kmp算法通俗易懂版
 * @date 2021/4/21 1:06 下午
 */
public class KmpDemo {
    public static void main(String[] args) {
        String str1 = "ABCABCD ABCDABCABCABCDE";
        String str2 = "ABCABCA";//[-1,0,0,0,1,2,3,0]
//        String str2 = "abcabd";
//        String str2 = "abcabcba";
//        这个是区分大小写的，因为比较用的==号，比较的是ASCII值，
//        如果要不区分大小写，需要在比较的时候，用equalsIgnoreCaseA
        //        String str2 = "abc";
        //先构建字符匹配表，后面的匹配过程，只需要查表即可
        int[] next = getNext(str2);
        System.out.println("字符匹配表是：" + Arrays.toString(next));
        int i = KmpSearch(str1, str2, next);
        System.out.println("找到的位置是：" + i);
    }

    /**
     * 传入一个字符串，返回字符匹配表
     *
     * @param str2 要生成匹配表的字符串
     * @return 返回匹配表数组
     */

    public static int[] getNext(String str2) {
        int[] next = new int[str2.length()];
        // 第一位，匹配值为0
        next[0] = -1;
        next[1] = 0;
        //j表示从第一位开始，i表示要对比的位置
        for (int i = 2, j = 0; i < next.length; i++) {
            while (str2.charAt(i - 1) != str2.charAt(j) && j != 0) {
                /**
                 * 这里是关键点
                 * 推荐视频:https://www.bilibili.com/video/BV16X4y137qw
                 * 跳到14：18看图解就懂了，我看了六遍
                 */
                j = next[j];
            }

            if (str2.charAt(i - 1) == str2.charAt(j)) {
                j++;
            }
            next[i] = j;
        }
        return next;
    }

    /**
     * kmp算法字符匹配的部分
     *
     * @param str1 源字符串
     * @param str2 要被匹配的字符串
     */
    public static int KmpSearch(String str1, String str2, int[] next) {
        // 查找匹配位置
        for (int i = 0, j = 0; i < str1.length(); i++) {
            while (str1.charAt(i) != str2.charAt(j) && j > 0){
                j = next[j];
            }

            if(str1.charAt(i) == str2.charAt(j)){
                /**
                 * 当最后一位数相等的时候，就不要再让他做++操作了
                 * 此时刚刚好i往前走了j步
                 */
                if (j == str2.length() - 1){
                    return i - j + 1;
                }
                j++;
            }
        }
        return -1;
    }
}

逸帅

niebaohua 发表于 2021-4-20 17:21
获取 部分匹配值好像不太对
例如：字符串 `aabaaac`

这一段的kmp匹配表，我好像只做了第一次的判断，后面的判断没有做，所以返回的值会存在错误，我昨天发现的这个问题，在准备改

逸帅

我弄个kmp算法讲解的视频，上传到动画区去

好好学习多挣钱

感谢，昨天刚学习到kmp

逸帅

好好学习多挣钱 发表于 2021-4-7 20:40
感谢，昨天刚学习到kmp

怎么样，学懂了没，主要是代码，写出来没

goodista

感谢，分享 有学习到

zgzxp

高手，学习了。
这个就是造轮子吗？

Loker

我大一的课程设计题目就是关于kmp算法

StephenLujc

厉害了楼主，最近刚好在学kmp算法，学习了~

niebaohua

清晰明了，之前都没怎么学过算法。

shiory

有点意思哦，看一遍就理解了，又学到了非常感谢。