算法日记day 11(KMP算法)

一、KMP算法

基本原理:

KMP算法(Knuth-Morris-Pratt算法)是一种用于在一个文本串(字符串)中查找一个模式串(子串)的高效算法。它的主要优点是在匹配过程中避免了回溯(backtracking),从而提高了匹配的效率。在字符串匹配算法中,通过求解最长相等前后缀来解决不匹配的情况,利用前缀表记录每个位置的最长相等前后缀,这种方法称为KMP算法。

KMP算法的核心思想:

  1. 部分匹配表(Partial Match Table)

    • KMP算法的关键在于构建部分匹配表,也称为最长前缀匹配表(Longest Prefix which is also Suffix, LPS)。这张表记录了模式串中每个前缀的最长匹配前缀长度。
    • 通过部分匹配表,可以根据已经匹配的部分信息,快速调整模式串的位置,跳过不可能匹配的情况,从而避免不必要的比较。
  2. 匹配过程

    • 在匹配过程中,KMP算法会根据当前匹配的位置和部分匹配表来决定模式串的移动位置,以达到尽量减少匹配次数的目的。
    • 当匹配失败时,不会简单地将模式串向后移动一个位置,而是利用部分匹配表中的信息,将模式串移动到一个合适的位置再进行匹配,从而提高效率。

算法步骤概述:

  1. 构建部分匹配表

    • 根据模式串,构建部分匹配表,计算每个位置对应的最长匹配前缀长度。
  2. 匹配过程

    • 遍历文本串,同时根据部分匹配表调整模式串的位置,进行匹配。
    • 如果当前字符匹配成功,继续匹配下一个字符;如果匹配失败,根据部分匹配表移动模式串的位置,直到找到匹配或者完全匹配失败。

优点:

  • 避免回溯:KMP算法通过利用部分匹配表的信息,能够在模式串与文本串匹配过程中,减少不必要的比较,避免回溯到之前已经比较过的位置,从而提高了算法的效率。
  • 时间复杂度:KMP算法的时间复杂度为O(m + n),其中m为模式串长度,n为文本串长度,主要由构建部分匹配表和匹配过程决定。

那么如何用前缀表来进行匹配?什么是前缀表?前缀表如何求?

前缀表记录了模式串中每个位置的最长相等前后缀长度,使得在匹配失败时可以跳转到之前已匹配的位置继续匹配。这种方法相比于暴力匹配算法,时间复杂度从O(m*n)降低到了O(m+n)。

首先要理解什么是前缀,什么是后缀,前缀是包含首字母不包含尾字母的子串,后缀是包含尾字母不包含首字母的子串,以例子说明:

文本串:    "aabaabaaf"

模式串: "aabaaf"

KMP算法在匹配时,当第一次匹配后,文本串的"b"匹配模式串的"f"匹配失败,这是KMP算法的第二轮匹配会直接从模式串的"b"开始,匹配文本串的第二个"b",那么为什么是这样匹配的呢?为什么会直接从b开始匹配?这就是前缀表的功劳了。

对于模式串来说,它的前缀可以是 a,aa,aab,aaba,aabaa, 后缀可以是f,af,aaf,baaf,abaaf,正是遵循"最长相等前后缀的原则" ,以例子说明:

a的相等前后缀为0

aa的相等前后缀为1    (前缀a,后缀a)

aab的相等前后缀为0

aaba的相等前后缀为1   (前缀a,后缀a)

aabaa的相等前后缀为2     (前缀a,aa,后缀a,aa)

aabaaf的相等前后缀为0

最终得到的模式串前缀表为

(0,1,0,1,2,0)

 再我们第一轮找到不匹配的元素后,这时应该找前一位元素的最长相等前后缀是多少

文本串:    "aabaabaaf"

模式串: "aabaaf"

 前缀表: 010120

模式串中"f"的前一位是a,它的最长相等前后缀是2,那么这个2是什么意思?

它代表着子串"aabaa"中的一个两位后缀aa,同时也有着一个相等的两位前缀aa,由于匹配的后缀不相等造成冲突,因此需要去寻找与其相等的前缀,而前缀表中的这个2,就是下一次匹配时模式串的起始位置(下标), 2是相等前后缀的长度,现在已知了前缀,因此要从该相等前缀的下一个元素开始下一次串匹配。

 

这时第二次匹配为

 

文本串:    "aabaa  baaf"

模式串:       "aa  baaf"

 

这时匹配完成,KMP算法结束

总结:

KMP算法通过利用部分匹配表,避免了回溯,提高了模式串匹配的效率,特别适合于需要多次匹配模式串的场景,如字符串匹配、编辑距离计算等。

具体题目:

1、KMP算法经典应用

给你两个字符串 haystack 和 needle ,请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标(下标从 0 开始)。如果 needle 不是 haystack 的一部分,则返回  -1 

示例 1:

输入:haystack = "sadbutsad", needle = "sad"
输出:0
解释:"sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ,所以返回 0 。

示例 2:

输入:haystack = "leetcode", needle = "leeto"
输出:-1
解释:"leeto" 没有在 "leetcode" 中出现,所以返回 -1 。

代码:

首先创建next数组作为字符串的前缀表(前缀表的值统一减一)

public void getNext(int[] next, String s){int j = -1;             // 初始化 j 为 -1,表示当前没有匹配的前缀next[0] = j;            // 第一个位置的部分匹配值为 -1for (int i = 1; i < s.length(); i++){  // 从第二个字符开始遍历 s 字符串while(j >= 0 && s.charAt(i) != s.charAt(j + 1)){// 如果当前字符不匹配,并且 j 大于等于 0,则通过 next[j] 回溯 j 的值j = next[j];}if(s.charAt(i) == s.charAt(j + 1)){// 如果当前字符匹配,则 j 向前移动一位j++;}next[i] = j;         // 记录当前位置 i 处的最长匹配前缀的末尾字符在模式串中的位置}
}
  1. 初始化

    • j = -1:初始化 j 为 -1,表示当前没有匹配的前缀。
    • next[0] = j:设置 next 数组的第一个位置为 -1,因为第一个字符没有前缀。
  2. 循环计算 next 数组

    • for (int i = 1; i < s.length(); i++):从字符串 s 的第二个字符开始遍历到末尾。
    • while(j >= 0 && s.charAt(i) != s.charAt(j + 1))
      • 如果当前字符不匹配,并且 j 大于等于 0,则通过 next[j] 回溯 j 的值,直到找到一个可以继续匹配的位置或者 j 回溯到 -1
    • if(s.charAt(i) == s.charAt(j + 1))
      • 如果当前字符匹配,则将 j 向前移动一位 j++
    • next[i] = j
      • 将 j 的值赋给 next[i],即记录当前位置 i 处的最长匹配前缀的末尾字符在模式串中的位置。

 

 KMP算法

public int strStr(String haystack, String needle) {if (needle.length() == 0) {return 0;   // 如果 needle 为空字符串,则返回 0}int[] next = new int[needle.length()];  // 创建 next 数组,用于存储部分匹配表getNext(next, needle);  // 调用 getNext 方法,计算 needle 的部分匹配表int j = -1;  // 初始化 j 为 -1,表示当前没有匹配的前缀for (int i = 0; i < haystack.length(); i++) {while (j >= 0 && haystack.charAt(i) != needle.charAt(j + 1)) {// 如果当前字符不匹配,并且 j 大于等于 0,则通过 next[j] 回溯 j 的值j = next[j];}if (haystack.charAt(i) == needle.charAt(j + 1)) {// 如果当前字符匹配,则 j 向前移动一位j++;}if (j == needle.length() - 1) {return (i - needle.length() + 1);  // 如果 j 移动到 needle 的末尾,则找到匹配的起始位置}}return -1;  // 没有找到匹配的子串,返回 -1
}
  1. 参数和边界情况处理

    • strStr 方法接受两个字符串参数 haystack 和 needle,其中 haystack 是待搜索的主字符串,needle 是要搜索的子字符串。
    • 如果 needle 的长度为 0,直接返回 0,因为一个空的 needle 在任何位置都是匹配的起始位置。
  2. 初始化 next 数组

    • 创建一个 next 数组,用于存储 needle 字符串的部分匹配表。
  3. 计算部分匹配表

    • 调用 getNext(next, needle) 方法,这个方法计算并填充 next 数组,用于在匹配失败时快速确定下一次比较的位置。
  4. 主匹配循环

    • 使用两个指针 i 和 j 分别在 haystack 和 needle 中进行遍历和比较。
    • j 初始为 -1,表示当前没有匹配的前缀。
    • 遍历 haystack 中的每个字符,如果当前字符不匹配,并且 j 大于等于 0,则通过 next[j] 回溯 j 的值,直到找到一个可以继续匹配的位置或者 j 回溯到 -1
    • 如果当前字符匹配,则将 j 向前移动一位。
    • 如果 j 移动到 needle 的末尾 needle.length() - 1,则说明找到了完整的匹配子串,返回起始位置 (i - needle.length() + 1)
  5. 返回结果

    • 如果循环结束都没有找到匹配的子串,则返回 -1 表示未找到。

在java中提供有直接寻找子字符串的方法indexOf,如

public int strStr(String haystack, String needle) {return haystack.indexOf(needle);
}
  • indexOf 方法是 Java 字符串类 String 的方法,用于查找一个子字符串在原字符串中的位置。它从原字符串的开头开始,逐个位置尝试匹配子字符串,直到找到匹配或者遍历完整个字符串。
  • 如果找到了匹配的子字符串 needle,则返回第一次出现的索引位置。
  • 如果没有找到匹配的子字符串,则返回 -1

这段代码简单而有效地利用了 Java 提供的字符串方法来实现字符串搜索功能。它适用于大多数基本的字符串搜索需求,但需要注意的是,它并没有利用更高级的字符串匹配算法(如 KMP 算法)来提高效率,因此在大数据量或者复杂匹配模式的情况下,可能性能会受到影响。

 

2、重复的子字符串

题目:

给定一个非空的字符串 s ,检查是否可以通过由它的一个子串重复多次构成。

示例 1:

输入: s = "abab"
输出: true
解释: 可由子串 "ab" 重复两次构成。

示例 2:

输入: s = "aba"
输出: false

示例 3:

输入: s = "abcabcabcabc"
输出: true
解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)

思路:

这里仍采用KMP算法,在最长相等前后缀中,由重复子串组成的字符串中,最长相等前后缀不包含的子串就是最小重复子串

 这是为什么呢?如何寻找是关键

 

步骤一:因为 这是相等的前缀和后缀,t[0] 与 k[0]相同, t[1] 与 k[1]相同,所以 s[0] 一定和 s[2]相同,s[1] 一定和 s[3]相同,即:,s[0]s[1]与s[2]s[3]相同 。

步骤二: 因为在同一个字符串位置,所以 t[2] 与 k[0]相同,t[3] 与 k[1]相同。

步骤三: 因为 这是相等的前缀和后缀,t[2] 与 k[2]相同 ,t[3]与k[3] 相同,所以,s[2]一定和s[4]相同,s[3]一定和s[5]相同,即:s[2]s[3] 与 s[4]s[5]相同。

步骤四:循环往复。

所以字符串s,s[0]s[1]与s[2]s[3]相同, s[2]s[3] 与 s[4]s[5]相同,s[4]s[5] 与 s[6]s[7] 相同。

正是因为 最长相等前后缀的规则,当一个字符串由重复子串组成的,最长相等前后缀不包含的子串就是最小重复子串。

此时数组对应的next数组的值为:

数组:a b a b a b a b

next[]: 0 0 1 2 3 4 5 6

 再比如:

判断子字符串是否重复,只需要用数组长度减去最长相同前后缀的长度相当于是第一个周期的长度,也就是一个周期的长度,如果这个周期可以被整除,就说明整个数组就是这个周期的循环

//创建next数组
for (int i = 2, j = 0; i <= len; i++) {// 匹配不成功,j回到前一位置 next 数组所对应的值while (j > 0 && chars[i] != chars[j + 1]) j = next[j];// 匹配成功,j往后移if (chars[i] == chars[j + 1]) j++;// 更新 next 数组的值next[i] = j;
}

 判断是否为重复子字符串

if (next[len] > 0 && len % (len - next[len]) == 0) {return true;
}

 完整代码如下:

public boolean repeatedSubstringPattern(String s) {if (s.equals("")) return false;int len = s.length();// 原串加个空格(哨兵),使下标从1开始,这样j从0开始,也不用初始化了s = " " + s;char[] chars = s.toCharArray();int[] next = new int[len + 1];// 构造 next 数组过程,j从0开始(空格),i从2开始for (int i = 2, j = 0; i <= len; i++) {// 匹配不成功,j回到前一位置 next 数组所对应的值while (j > 0 && chars[i] != chars[j + 1]) j = next[j];// 匹配成功,j往后移if (chars[i] == chars[j + 1]) j++;// 更新 next 数组的值next[i] = j;}// 最后判断是否是重复的子字符串,这里 next[len] 即代表next数组末尾的值if (next[len] > 0 && len % (len - next[len]) == 0) {return true;}return false;
}

 

  1. 边界条件

    • if (s.equals("")) return false; 如果输入的字符串 s 是空字符串,则直接返回 false,因为空字符串不可能由重复的子字符串构成。
  2. 初始化

    • int len = s.length(); 获取字符串 s 的长度。
    • s = " " + s; 在字符串 s 的开头加上一个空格作为哨兵,使得字符串的索引从 1 开始,这样方便后续算法中的处理。
  3. 构造 next 数组

    • char[] chars = s.toCharArray(); 将字符串 s 转换为字符数组 chars,便于随后的字符操作。
    • int[] next = new int[len + 1]; 创建 next 数组,用于存储部分匹配表。
  4. KMP 算法核心部分

    • for (int i = 2, j = 0; i <= len; i++) { ... } 使用 i 和 j 两个指针,其中 i 表示当前正在匹配的位置,j 表示前缀的匹配长度。
    • while (j > 0 && chars[i] != chars[j + 1]) j = next[j]; 如果当前字符不匹配,并且 j 大于 0,则通过 next[j] 回溯 j 的值,直到找到一个可以继续匹配的位置。
    • if (chars[i] == chars[j + 1]) j++; 如果当前字符匹配,则将 j 向后移动一位。
    • next[i] = j; 更新 next 数组的值,表示当前位置的最长相同前缀后缀长度。
  5. 判断重复子字符串

    • if (next[len] > 0 && len % (len - next[len]) == 0) { return true; } 
      • next[len] 表示整个字符串的最长相同前缀后缀长度。
      • len % (len - next[len]) == 0 表示字符串长度能整除最长前缀后缀的长度,即可以由子字符串重复构成。
      • 如果上述条件满足,则返回 true,否则返回 false

 相关资料来源:

https://www.programmercarl.com/0459.%E9%87%8D%E5%A4%8D%E7%9A%84%E5%AD%90%E5%AD%97%E7%AC%A6%E4%B8%B2.html#%E6%80%9D%E8%B7%AF

https://leetcode.cn/problems/repeated-substring-pattern/

 今天的学习就到这里了

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/379802.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

新版网页无插件H.265播放器EasyPlayer.js如何测试demo视频?

H5无插件流媒体播放器EasyPlayer属于一款高效、精炼、稳定且免费的流媒体播放器&#xff0c;可支持多种流媒体协议播放&#xff0c;支持H.264与H.265编码格式&#xff0c;性能稳定、播放流畅&#xff1b;支持WebSocket-FLV、HTTP-FLV&#xff0c;HLS&#xff08;m3u8&#xff0…

cleanshot Mac 上的截图工具

笔者闲来无事&#xff0c;最近在找一些mac上好用的工具其中一款就是cleanShot。为什么不用原有的mac自带的呢。因为相对来说编辑功能不算全面&#xff0c;不支持长截图。那有没有一款软件支持关于截图的好用工具呢。 所以笔者找了这款。安装包是直接安装就可使用的。请大家点赞…

MATLAB quiver矢量图 设置colorbar

给三维矢量图按照不同高度设置箭头颜色 figure clf X surfaceuz(:,1); Y surfaceuz(:,2); Z surfaceuz(:,3); hold onzcolor jet; % qquiver3(X,Y,Z,X,Y,W) for i 1:length(surfaceuz)quiver3(X(i),Y(i),Z(i),X(i),Y(i), Z(i),...Color,zcolor(floor((Z(i) - -0.1) * 2…

【Linux学习】常用基本指令

&#x1f525;个人主页&#xff1a; Forcible Bug Maker &#x1f525;专栏&#xff1a;Linux学习 目录 &#x1f308;前言&#x1f525;XShell的一些使用查看Linux主机IP使用XShell登录主机XShell下的复制粘贴 &#x1f525;Linux下常用基本指令ls指令pwd指令cd指定touch指令…

【JVM基础02】——组成-程序计数器解读

目录 1- 引言&#xff1a;程序计数器1-1 程序计数器是什么&#xff1f;为什么用程序计数器&#xff1f;(What)(Why) 2- 核心&#xff1a;程序计数器的原理&#xff08;How&#xff09;2-1 使用 javap 查看程序计数器的作用2-2 多线程下程序计数器原理举例 3- 小结&#xff1a;什…

完美解决ImportError: cannot import name ‘PILLOW_VERSION‘的正确解决方法,亲测有效!!!

完美解决ImportError: cannot import name PILLOW_VERSION’的正确解决方法&#xff0c;亲测有效&#xff01;&#xff01;&#xff01; 亲测有效 完美解决ImportError: cannot import name PILLOW_VERSION的正确解决方法&#xff0c;亲测有效&#xff01;&#xff01;&#xf…

专业PDF编辑工具:Acrobat Pro DC 2024.002.20933绿色版,提升你的工作效率!

软件介绍 Adobe Acrobat Pro DC 2024绿色便携版是一款功能强大的PDF编辑和转换软件&#xff0c;由Adobe公司推出。它是Acrobat XI系列的后续产品&#xff0c;提供了全新的用户界面和增强功能。用户可以借助这款软件将纸质文件转换为可编辑的电子文件&#xff0c;便于传输、签署…

pdf提取其中一页怎么操作?提取PDF其中一页的方法

pdf提取其中一页怎么操作&#xff1f;需要从一个PDF文件中提取特定页码的操作通常是在处理文档时常见的需求。这种操作允许用户选择性地获取所需的信息&#xff0c;而不必操作整个文档。通过选择性提取页面&#xff0c;你可以更高效地管理和利用PDF文件的内容&#xff0c;无论是…

通过docker构建基于LNMP的WordPress项目

目录 1.准备nginx 2.准备mysql 3.准备php 4.构建各镜像 5.运行wordpress 1、项目环境&#xff1a; 1.1 &#xff08;1&#xff09;公司在实际的生产环境中&#xff0c;需要使用Docker 技术在一台主机上创建LNMP服务并运行Wordpress网站平台。然后对此服务进行相关的性能…

01数据结构 - 顺序表

这里是只讲干货不讲废话的炽念&#xff0c;这个系列的文章是为了我自己以后复习数据结构而写&#xff0c;所以可能会用一种我自己能够听懂的方式来描述&#xff0c;不会像书本上那么枯燥和无聊&#xff0c;且全系列的代码均是可运行的代码&#xff0c;关键地方会给出注释^_^ 全…

大数据面试SQL题-笔记01【运算符、条件查询、语法顺序、表连接】

大数据面试SQL题复习思路一网打尽&#xff01;(文档见评论区)_哔哩哔哩_bilibiliHive SQL 大厂必考常用窗口函数及相关面试题 大数据面试SQL题-笔记01【运算符、条件查询、语法顺序、表连接】大数据面试SQL题-笔记02【...】 目录 01、力扣网-sql题 1、高频SQL50题&#xff08…

51单片机STC89C52RC——19.1 SG90舵机(伺服电机)

目的/效果 独立按键K1&#xff0c;K2 实现加舵机减角度增减&#xff0c;LCD1602显示舵机转角度数&#xff08;上电默认90度&#xff09; 一&#xff0c;STC单片机模块 二&#xff0c;SG90舵机 2.1 简介 舵机只是我们通俗的叫法&#xff0c;它的本质是一个伺服电机&#xf…

VPN以及GRE和MGRE

VPN VPN — 是虚拟专用网络 通俗地说&#xff0c;就是通过虚拟的手段&#xff0c;将两个独立的网络&#xff0c;穿越一个公共网络进行连接&#xff0c;实现点到点专线的效果&#xff08;可以理解为&#xff1a;一个分公司通过公网和总公司建立点到点的专线连接&#xff09; 现…

【MQTT(3)】开发一个客户端,QT-Android安卓手机版本

手机版本更加方便 生成安卓库 参考了这个代码 在编译Mosquitto以支持安卓平台时&#xff0c;主要涉及到使用Android NDK&#xff08;Native Development Kit&#xff09;进行交叉编译。环境的准备参考之前的博客【QT开发&#xff08;17&#xff09;】2023-QT 5.14.2实现Andr…

单链表算法 - 链表的回文结构

链表的回文结构_牛客题霸_牛客网对于一个链表&#xff0c;请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法&#xff0c;判断其是否为。题目来自【牛客题霸】https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa思路1: /* struct ListNode {int val;st…

字节面试:如何让单机下Netty支持百万长连接?

最近有同学在面试遇到了一道非常有深度的面试题&#xff1a; 如何让单机下Netty支持百万长连接&#xff1f; 当时在群里问小北&#xff0c;我发现我也没有系统化的梳理过这个问题&#xff0c;所以一时也没有回答的特别好。 痛定思痛的我赶紧去各种搜集资料&#xff0c;系统化的…

unity渲染人物模型透明度问题

问题1&#xff1a;有独立的手和衣服的模型&#xff0c;但最终只渲染出来半透明衣服 问题2&#xff1a;透明度贴图是正确的但显示却不正确 这上面两个模型的问题都是因为人物模型是一个完整的&#xff0c;为啥有些地方可以正常显示&#xff0c;有些地方透明度却有问题。 其中…

数据结构小测试:排序算法

目录 1、请简述数据结构八大排序算法的思路。 2、常用排序算法手写 冒泡排序&#xff1a; 选择排序&#xff1a; 快速排序&#xff1a; 归并排序&#xff1a; 堆排序&#xff1a; 3、额外再加一个二分查找吧 1、请简述数据结构八大排序算法的思路。 冒泡排序&#xff…

亚信安全发布2024年第24期《勒索家族和勒索事件监控报告》

本周态势快速感知 本周&#xff0c;勒索软件LockBit涉嫌对美国一家生产乙烯基产品的公司&#xff08;Homeland Vinyl&#xff09;进行攻击。LockBit声称他们已窃取了销售、库存、财务交易数据及其他公司记录&#xff0c;并声明将于2024年7月19日公开这些被盗信息。本周全球共监…

【iOS】OC类与对象的本质分析

目录 前言clang常用命令对象本质探索属性的本质对象的内存大小isa 指针探究 前言 OC 代码的底层实现都是 C/C代码&#xff0c;OC 的对象都是基于 C/C 的数据结构实现的&#xff0c;实际 OC 对象的本质就是结构体&#xff0c;那到底是一个怎样的结构体呢&#xff1f; clang常用…