字符串匹配-KMP算法

这篇具有很好参考价值的文章主要介绍了字符串匹配-KMP算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

KMP算法,字符串匹配算法,给定一个主串S,和一个字串T,返回字串T与之S匹配的数组下标。

在学KMP算法之前,对于两个字符串,主串S,和字串T,我们根据暴力匹配,定义两个指针,i指向主串S的起始,j指向字串T的起始,依次比较,如果主串i位置的值等于子串j位置的值,i++,j++。直到i位置的值和j位置的值不相同,i回溯到起始位置+1,同时字串T的起始位置后移到i所在位置。直到匹配成功,或者子串T后移长度+T本身长度>S主串的长度。这个暴力求解的复杂度,因为有i的回溯,需要2层循环i,j的移动,因此时间复杂度为T(n*m),n是S的长度,m是T的长度。

根据暴力匹配的思想,我们接下来分析一下KMP算法。同样两个字符串按位比较,而KMP算法的核心在于,当主串的i位置的值和子串的j位置的值不同时,主串S,i前面的字符串与字串T,j前面的字符串已经匹配相等,因为两者相等,所以只需要拿出子串T前面的字符串,根据T前面的字符串来计算一个next[j]数组,将j回溯即可。问题便转换为求子串的next[j]数组。那么next[j]数组的求法为,i前面的字符串,分别取前缀和取后缀,如果前缀的长度=后缀的长度,则j的值=字符串缀长+1存入next数组。否则,j回溯给next[j]。直到j=字串长度,则next数组计算完成。后续根据i不回溯,j从next数组里取值,便可将字串T和主串S进行匹配,直到字串T移出到主串S的长度,匹配成功返回i-j下标,匹配失败返回-1。因为KMP算法简化了问题的求解,将难点转换为求next数组,并且i不回溯,可以做到边移动边匹配。因此,时间复杂度为T(n+m)

下面给两个实例:

1:给定2个字符串,主串S,子串T,如果T匹配S,则返回在S当中的下标。

  public static void main(String[] args) {

        String S  = "abababcabcabc";
        String T  = "bcabc";


        int pos = KMP(S,T);

        System.out.println(pos);


    }

    private static int KMP(String s, String t) {
        int i = 0;//i指向S
        int j = 0;//j指向T

        while (i<s.length()&&j<t.length()){
            if(j==-1||s.charAt(i)==t.charAt(j)){//为什么j==-1,i和j也需要后移,当j==-1,说明字串和主串的起始点在0,
                i++;//i后移
                j++;//j后移
            }else{
                j = getNext(t)[j]; //j根据t求一个next数组,next数组的作用就是j根据内部的值回溯。
            }
        }

        if(j == t.length()){  //j已经等于t的长度了,说明匹配结束了。
            return i-t.length();  //字串起始点就是i-j或者i-t.length()
        }else{
            return -1;//匹配失败了。
        }

    }

    private static int[] getNext(String t) {
        int i = 0;//next数组下标,初始值0
        int j = -1;//j指向字符串t,初始值-1
        int [] next = new int[t.length()];//构造next数组,长度为t的长度。
        next[0] = -1;//next数组从1开始存值,即0号位置存默认值-1;
        while (i<t.length()-1){
            if(j==-1||t.charAt(i)==t.charAt(j)){//j==-1表示从头开始遍历t,或者t的前缀==t的后缀,都要将j+1存入next数组
               i++;
               j++;
               next[i] =  j;  //如果后缀==前缀,将j+1,即j++的值存入next数组。
            }else {
               j = next[j]; //如果后缀!=前缀,j回溯到next[j]位置
            }
        }
        return next;
    }

输出结果:

5

完全正确。

2:给定2个字符串,主串S,子串T,返回子串T在主串S中出现的次数。

求次数的问题,将原生KMP算法,变化为,当j==t.length()的时候,匹配有效,计数器count++,j回溯到next数组的j-1位置上,再对其+1。+1的目的是next数组值=子串前缀/后缀的长度+1

    public static void main(String[] args) {

        String S  = "abababcabcabc";
        String T  = "bcabc";


        int count= KMP(S,T);

        System.out.println(count);


    }

    private static int KMP(String s, String t) {
        int i = 0;//i指向S
        int j = 0;//j指向T
        int count = 0;//计数器
        int[] next = getNext(t);

        while (i<s.length()&&j<t.length()){
            if(j==-1||s.charAt(i)==t.charAt(j)){//为什么j==-1,i和j也需要后移,当j==-1,说明字串和主串的起始点在0,
                i++;//i后移
                j++;//j后移
            }else{
                j = next[j]; //j根据t求一个next数组,next数组的作用就是j根据内部的值回溯。
            }
            if(j==t.length()){//匹配到了
                count++;//计数器++
                j = next[j-1]+1;//j回溯到next数组的[j-1]=前缀长度,而j的值=对其+1
            }
        }
        return count;
    }

    private static int[] getNext(String t) {
        int i = 0;//next数组下标,初始值0
        int j = -1;//j指向字符串t,初始值-1
        int [] next = new int[t.length()];//构造next数组,长度为t的长度。
        next[0] = -1;//next数组从1开始存值,即0号位置存默认值-1;
        while (i<t.length()-1){
            if(j==-1||t.charAt(i)==t.charAt(j)){//j==-1表示从头开始遍历t,或者t的前缀==t的后缀,都要将j+1存入next数组
                i++;
                j++;
                next[i] =  j;  //如果后缀==前缀,将j+1,即j++的值存入next数组。
            }else {
                j = next[j]; //如果后缀!=前缀,j回溯到next[j]位置
            }
        }
        return next;
    }

输出结果

2

 求出现次数区别在于这里的不同:

字符串匹配-KMP算法,数据结构与算法,算法文章来源地址https://www.toymoban.com/news/detail-623976.html

到了这里,关于字符串匹配-KMP算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • C#,字符串匹配(模式搜索)KMP算法的源代码与数据可视化

      D.E.Knuth   J.H.Morris KMP 算法(Knuth-Morris-Pratt 算法)是其中一个著名的、传统的字符串匹配算法,效率比较高。 KMP算法由 D.E.Knuth , J.H.Morris 和 V.R.Pratt 在 Brute-Force 算法的基础上提出的模式匹配的改进算法。因此人们称它为“克努特—莫里斯—普拉特算法”,简称KMP算法。K

    2024年01月25日
    浏览(29)
  • 字符串匹配算法(BF&&KMP)

    个人主页:平行线也会相交 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 平行线也会相交 原创 收录于专栏【数据结构初阶(C实现)】 在学习这个算法之前,我们先来看看什么时字符串匹配算法,简单来说 有一个主串和一个子串,查找子串在主串的位置,然后返回这个位置

    2023年04月17日
    浏览(20)
  • 【数据结构】数组和字符串(十四):字符串匹配1:朴素的模式匹配算法(StringMatching)

      字符串(String)是由零个或多个字符(char)顺序排列组成的有限序列,简称为串。例如 “good morning”就是由12个字符构成的一个字符串。一般把字符串记作: S = ′ ′ a 0 a 1 … a n − 1 ′ ′ S=\\\'\\\'a_{0} a_{1}…a_{n-1}\\\'\\\' S = ′′ a 0 ​ a 1 ​ … a n − 1 ′′ ​   其中S是串名,引号中

    2024年02月05日
    浏览(41)
  • 数据结构课设:基于字符串模式匹配算法的病毒感染检测问题

    1.掌握字符串的顺序存储表示方法。 2.掌握字符串模式匹配算法BF算法或KMP算法的实现。 问题描述 医学研究者最近发现了某些新病毒,通过对这些病毒的分析,得知它们的DNA序列都是环状的。现在研究者已收集了大量的病毒DNA和人的DNA数据,想快速检测出这些人是否感染了

    2023年04月27日
    浏览(28)
  • P3375 【模板】KMP 字符串匹配

    给出两个字符串 s 1 s_1 s 1 ​ 和 s 2 s_2 s 2 ​ ,若 s 1 s_1 s 1 ​ 的区间 [ l , r ] [l, r] [ l , r ] 子串与 s 2 s_2 s 2 ​ 完全相同,则称 s 2 s_2 s 2 ​ 在 s 1 s_1 s 1 ​ 中出现了,其出现位置为 l l l 。 现在请你求出 s 2 s_2 s 2 ​ 在 s 1 s_1 s 1 ​ 中所有出现的位置。 定义一个字符串 s s s 的

    2024年02月14日
    浏览(29)
  • PTA 7-1 字符串模式匹配(KMP)

    给定一个字符串 text 和一个模式串 pattern,求 pattern 在text 中的出现次数。text 和 pattern 中的字符均为英语大写字母或小写字母。text中不同位置出现的pattern 可重叠。 输入格式: 输入共两行,分别是字符串text 和模式串pattern。 输出格式: 输出一个整数,表示 pattern 在 text 中的出

    2024年02月06日
    浏览(22)
  • 【leetcode 力扣刷题】字符串匹配之经典的KMP!!!

    以下是能用KMP求解的算法题,KMP是用于字符串匹配的经典算法【至今没学懂………啊啊啊】 题目链接:28. 找出字符串中第一个匹配项的下标 题目内容: 题意还是很好理解的,要在字符串haystack中查找一个完整的needle,即字符串匹配。 暴力求解就是用 两层循环 :haystack从第

    2024年02月09日
    浏览(23)
  • Leetcode的AC指南 —— 字符串/KMP:28.找出字符串中第一个匹配项的下标

    摘要: Leetcode的AC指南 —— 字符串/KMP:28.找出字符串中第一个匹配项的下标 。题目介绍:给你两个字符串 haystack 和 needle ,请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标(下标从 0 开始)。如果 needle 不是 haystack 的一部分,则返回 -1 。 题目介绍 :给你两

    2024年02月02日
    浏览(37)
  • LeetCode:459. 重复的子字符串 —【2、KMP算法】

    🍎道阻且长,行则将至。🍓 🌻算法,不如说它是一种思考方式🍀 算法专栏: 👉🏻123 题目描述 :给定一个非空的字符串 s ,检查是否可以通过由它的一个子串重复多次构成。 来源:力扣(LeetCode) 难度: 简单 提示: 1 = s.length = 104 s 由小写英文字母组成 示例 1: 输入:

    2024年02月04日
    浏览(32)
  • 【JavaScript数据结构与算法】字符串类(反转字符串中的单词)

    个人简介 👀 个人主页: 前端杂货铺 🙋‍♂️ 学习方向: 主攻前端方向,也会涉及到服务端(Node.js) 📃 个人状态: 在校大学生一枚,已拿多个前端 offer(秋招) 🚀 未来打算: 为中国的工业软件事业效力 n 年 🥇 推荐学习:🍍前端面试宝典 🍉Vue2 🍋Vue3 🍓Vue2/3项目

    2023年04月09日
    浏览(64)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包