首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >字符串匹配算法之KMP

字符串匹配算法之KMP

作者头像
沁溪源
发布2020-09-03 14:36:24
6560
发布2020-09-03 14:36:24
举报
文章被收录于专栏:沁溪源沁溪源

目录

  • 需求
  • 基础知识
  • 逻辑解析
  • 源码实现

需求

先简单描述溪源曾经遇到的需求:

需求一:项目结果文件中实验结论可能会存在未知类型、转换错误、空指针、超过索引长度等等。这里是类比需求,用日常开发中常出现的错误类型作为需求,如果要以上结论则判断这个项目检测失败;

解决方案一: 大家常用的方式可能是if(){continue;} esle if (){continue;} …或者switch-case等;

方案二:可能会使用集合contain()方法;

方案三:依次匹配字符串中字符(暴力匹配);

以上两种方案都能解决;然后大家需要考虑性能、维护和代码整洁性,可能居多使用方案二;

需求二:项目结论中即存在正常、成功的结论,又存在以上列举的失败字段;

例如:

//存在异常错误
String str1 = "正常范围内;转换错误";

//存在异常错误
String str2 = "i=20空指针;超出索引长度;j正常";

//正常值
String str3 = "i=30;j值正常";

...等等

面对这种需求,大家可能会想到split()方法之后再判断是否正常等等…相信大家总是会有办法解决的。不再列举了,面对产品经理各种需求大家尽情发挥脑洞吧,那么开始进入今天的正题,溪源采用KMP字符串匹配算法解析此需求。

基础知识

根据上面介绍的需求,大家应该会对KMP算法解决的问题稍有理解。

KMP算法解决的问题:在字符串(主串)中是否能够定位出模式串(子串)。 上面提及到暴力匹配字符串,为什么不使用呢?时间复杂度O(m*n),而KMP算法时间复杂度为O(m+n)。

再介绍几个概念性的知识:

  • 前缀:除最后一位以外,第一位依次与其余字符组成的字符串集合;
  • 后缀:除第一位以外最后一位依次与其余字符组成的字符串集合;

简单举例:

字符串ABCD,其前缀:A,AB,ABC; 后缀: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。

综上可以得出下面的表格:

搜索串

A

B

C

D

A

B

D

部分匹配值

0

0

0

0

1

2

0

逻辑解析

经历过上面的基础知识介绍后,下面开始一步步逻辑解析整个匹配过程:

  1. 字符串"BBC ABCDAB ABCDABCDABDE"的第一个字符与搜索串(模式串,以下简称P串)"ABCDABD"的第一个字符,进行比较。
在这里插入图片描述
在这里插入图片描述
  1. 由于B与A字符不匹配,P串整体再往后移动一位与主串比较。
在这里插入图片描述
在这里插入图片描述
  1. 此时主串第二位字符B与搜索串第一位A依然不匹配,P串再继续移动…,直至主串存在与P串第一个字符匹配。
在这里插入图片描述
在这里插入图片描述
  1. 依次比较P串与主串的字符是否匹配。
在这里插入图片描述
在这里插入图片描述
  1. 匹配过程中存在与主串存在不匹配字符。
在这里插入图片描述
在这里插入图片描述
  1. 此时,大家应该是将P串再次整个后移一位,再从头逐个比较,如下图所示。虽然此种方式有效,但是效率很差,因为要把"搜索位置"移到已经比较过的位置,再次重比一遍。
在这里插入图片描述
在这里插入图片描述
  1. 从5点可以明确知道,P串中字符D与主串空格不匹配时,其实字符D之前已经匹配的六个字符是已知的。因此KMP算法思想就是利用这个已知信息,不要重复比较已经比较过的位置,而是继续将P串向后移动几位。 重点来了,向后移动几位呢?此时便用到了上面介绍的部分匹配表

移动位数=已匹配的字符数-最后一个匹配字符对应的部分匹配值 因此,第5点之后,主串中空格与P串字符D字符不匹配时,已匹配字符为6个,最后一个以匹配字符B对应的部分匹配值为2,因此P串应该移动的位数为6-2=4。如图:

在这里插入图片描述
在这里插入图片描述

8. 空格与字符C不匹配,因此P串继续往后移。计算移动位数:已匹配的字符数为2(“AB”),对应的"部分匹配值"为0。所以,移动位数 = 2 - 0,结果为 2。

在这里插入图片描述
在这里插入图片描述

9. 空格与A不匹配,继续后移一位。

在这里插入图片描述
在这里插入图片描述

10. 逐位比较,直到发现C与D不匹配。于是,移动位数 = 6 - 2,继续将搜索词向后移动4位。

在这里插入图片描述
在这里插入图片描述

11. 逐位比较,直到搜索词的最后一位,发现完全匹配,于是搜索完成。如果还要继续搜索(即找出全部匹配),移动位数 = 7 - 0,再将搜索词向后移动7位,这里就不再重复了。

源码实现

public class Kmp {
    /**
     *
     * @param originString 源字符串
     * @param subString 子串
     * @param next 部分匹配表, 是子串对应的部分匹配表
     * @return 如果是-1 就是没有匹配到,否则返回第一个匹配的位置
     */
    public static int kmpSearch(String originString, String subString, int[] next) {
        for (int i = 0, j = 0; i < originString.length(); i++) {
            while (j > 0 && originString.charAt(i) != subString.charAt(j)) {
                j = next[j - 1];
            }

            if (originString.charAt(i) == subString.charAt(j)) {
                j++;
            }
            if (j == subString.length()) {
                return i - j + 1;
            }
        }
        return -1;
    }

    /**
     *获取到一个字符串(子串) 的部分匹配值表(前缀、后缀共同元素的长度)
     * @param dest 子串
     * @return
     */
    public static int[] kmpNext(String dest) {
        //创建一个 next 数组保存部分匹配值
        int[] next = new int[dest.length()];
        //如果字符串是长度为 1 部分匹配值就是 0
        next[0] = 0;
        for (int i = 1, j = 0; i < dest.length(); i++) {
            while (j > 0 && dest.charAt(i) != dest.charAt(j)) {
                j = next[j - 1];
            }
            //当 dest.charAt(i) == dest.charAt(j) 满足时,部分匹配值就是+1
            if(dest.charAt(i) == dest.charAt(j)) {
                j++;
            }
            next[i] = j;
        }
        return next;
    }


    public static boolean matcherResult(String originString, List<String> unknownList) {
        boolean unknown = false;
        for (String unknownConclusion : unknownList) {
            int[] kmpNext = kmpNext(originString);
            int index = kmpSearch(originString, unknownConclusion, kmpNext);
            if (index != -1) {
                unknown = true;
                break;
            }
        }
        return unknown;
    }

}

参考资料:http://jakeboxer.com/blog/2009/12/13/the-knuth-morris-pratt-algorithm-in-my-own-words/

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2020-07-22 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 目录
  • 需求
  • 基础知识
  • 逻辑解析
  • 源码实现
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档