吾爱破解 - LCG - LSG |安卓破解|病毒分析|www.52pojie.cn

 找回密码
 注册[Register]

QQ登录

只需一步,快速开始

查看: 2231|回复: 20
收起左侧

[Java 转载] KMP算法

[复制链接]
逸帅 发表于 2021-4-7 20:15
本帖最后由 逸帅 于 2021-4-21 19:18 编辑

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。

如下表:
12.png

2.2.2、匹配过程

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

步骤:

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

image-20210407164651730.png

  1. 重复第一步,还是不符合,再后移

image-20210407164702106.png

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

image-20210407164713345.png

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

image-20210407164733122.png

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

image-20210407164741945.png

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

image-20210407165142769.png

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

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

image-20210407165255432.png

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

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

image-20210407165509817.png

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

image-20210407165659177.png

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

image-20210407165911665.png

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

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;
    }
}

免费评分

参与人数 4吾爱币 +4 热心值 +4 收起 理由
QingYi. + 2 + 1 优秀 真真正正花精力来做
niebaohua + 1 + 1 谢谢@Thanks!
笨笨家的唯一 + 1 我很赞同!
好好学习多挣钱 + 1 + 1 我很赞同!

查看全部评分

发帖前要善用论坛搜索功能,那里可能会有你要找的答案或者已经有人发布过相同内容了,请勿重复发帖。

 楼主| 逸帅 发表于 2021-4-20 19:04
niebaohua 发表于 2021-4-20 17:21
获取 部分匹配值好像不太对
例如:字符串 `aabaaac`

这一段的kmp匹配表,我好像只做了第一次的判断,后面的判断没有做,所以返回的值会存在错误,我昨天发现的这个问题,在准备改
 楼主| 逸帅 发表于 2021-4-7 20:16
好好学习多挣钱 发表于 2021-4-7 20:40
 楼主| 逸帅 发表于 2021-4-7 20:53
好好学习多挣钱 发表于 2021-4-7 20:40
感谢,昨天刚学习到kmp

怎么样,学懂了没,主要是代码,写出来没
goodista 发表于 2021-4-7 20:58
感谢,分享 有学习到
zgzxp 发表于 2021-4-7 21:39
高手,学习了。
这个就是造轮子吗?
Loker 发表于 2021-4-7 21:47
我大一的课程设计题目就是关于kmp算法
StephenLujc 发表于 2021-4-7 21:59
厉害了楼主,最近刚好在学kmp算法,学习了~
niebaohua 发表于 2021-4-7 22:14
清晰明了,之前都没怎么学过算法。
shiory 发表于 2021-4-7 22:30
有点意思哦,看一遍就理解了,又学到了非常感谢。
您需要登录后才可以回帖 登录 | 注册[Register]

本版积分规则 警告:本版块禁止灌水或回复与主题无关内容,违者重罚!

快速回复 收藏帖子 返回列表 搜索

RSS订阅|小黑屋|处罚记录|联系我们|吾爱破解 - LCG - LSG ( 京ICP备16042023号 | 京公网安备 11010502030087号 )

GMT+8, 2024-3-29 06:21

Powered by Discuz!

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表