模式匹配
- 什么是模式匹配，我们用一个案例来说明：
- 当S = “s1,s2,s3,s4 …sn” T=“t1,t2,t3,t4 … tn” 在字符串S中寻找T字符串的过程就是模式匹配的过程，T就说模式串，S是主串
- 实现方案：
- 暴力破解，逐字符判断，直到找到对应的全匹配
- 由暴力破解的缺点逐步优化，引出KMP算法
- 思路如下：
- 令i 是目标串S的下标， j是模式串T的下标
- 当匹配到Si == Tj 的时候，我们做 i++，j++继续匹配下一个
- 当匹配到Si != Tj 的时候，我们需要冲头匹配，另 i = i - j + 1， j = 0
- 其中 i = i - j + 1 就说目标串S的回朔，我们匹配过j 个字符，那么回退 j个位置到当前这次匹配的最开始的位置，并且先前移动一位。
- 根据如上分析有如下代码：
/**
* Created by jiamin5 on 2022/2/12.
* 给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回-1 。
* 来源：力扣（LeetCode第28题）
* 链接：https://leetcode-cn.com/problems/implement-strstr
*/
public class StrKmp {
public static void main(String[] args) {
System.out.println(strBM("asdfuohadsuoufhuuowyqruoqiwhgbyur23iu4y2oi34hf", "uoq"));
}/**
* 模式匹配BM暴力破解写法
* */
public static int strBM(String haystack, String needle){
if (needle == null && haystack == null) {
return 0;
}
if (haystack == null || haystack.length() <= 0) {
return -1;
}
if (needle.isEmpty()) {
return 0;
}
if (haystack.length() < needle.length()) {
return -1;
}
char[] hasChar = haystack.toCharArray();
char[] needChar = needle.toCharArray();
int i = 0, j = 0;
while (i暴力破解算法分析
- 我们用一个特殊一点的案例来解释暴力破解算法
- 依然用i 表示目标串S：ab abc abcac bab， 用j 表示模式串T：abcac， 有如下流程
- 第一步，当Si， Tj 匹配到2 位置的时候，匹配是吧，i回朔到位置 2-2 +1 = 1，j=0
文章图片
- 第二次匹配第一个字符就失败，j=1-0+1=2
文章图片
- 第三次匹配，一直匹配到i= 6 的时候才匹配失败，这个时候，i=6-4+1 = 3，从第二个b开始匹配
文章图片
- 第四次从第二个b开始，显然是不可匹配到
文章图片
- 依次一直持续到第六次匹配，才匹配成功
文章图片
- 总结
- 在如上流程中，每次匹配失败我们都回将i 回朔到当前匹配批次的下一个位置，j又从0开始比较
- 在第三次匹配结束后，我们可以发现：i=3和j=0，i=4和j=0以及i=5和j=0是不必进行的
- 关键点在于，我们在第三次匹配的时候，已经知道了前面的串中有ab abcab，从中我们可以得出，主串中第3，4，5个字符必然是‘b’，‘c’，‘a’，与模式串T中的 1，2，3 字符是相同的，是可以没必要在匹配的
- 可以在第三步骤的时候，就知道，我们应该直接移动到i = 6 的位置，因为i = 6 的位置与j = 0 的位置都是 a 是想匹配的，之前的匹配过的字符已经是已知不可匹配的
- 依照如上分析：如果有一个类似的数组，用来辅助挑转位置，那么明显会加快进程。这样就引出了我们的KMP算法，不回溯i，加快匹配效率。
- KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n) [1] （自百度百科）
- 算法流程如下：
- 如果j = -1 ，i++，j++，继续匹配下一个字符
- 如果Si == Tj，i++， j++，继续匹配下一个字符
- 如果Si != Tj，且j != -1，i不变，j = next[j]，意味着在匹配失败的时候，接下来模式串T要相对于主串S向右移 j - next[j] 位置。
- 那么会出现如下几个问题：
- next是什么
- 怎么得到next
- 要了解next的来源，先得知道一个名字：最长公共前后缀。假设有一个串P=“P0P1P2P3…Pj-1Pj”如果存在P0P1P2…Pk-1Pk = Pj-kPj-k+1…Pj-1Pj，我们就可以说在P串中最大长度为k+1 的公共前后缀
- 找最大公共前后缀的意义：
- 例如在意思的案例中：ab abcabcac bac，我们在第三步骤中匹配到第一个abc，到第六步骤中匹配到第二个abc，在中间四，五步骤都在确认该字符：abcab，其中他的最长公共前后缀长度是，也就是ab
- 我们完全可以看出，单我们匹配到第一个abc的时候，完全可以直接跳过接下来的bc的匹配直接跳到第二个ab去匹配，那么最长公共前后缀就是这个作用，他告诉我们，在已经匹配过的字符串中，有没有这样的字符，我们直接跳过中间的字符，区匹配后面对于的字符ab就行了
- 还是用刚才那个案例字符串P = abaabca
文章图片
- 这样公共先后在最长长度会和P的每个字符有一个对应关系：
文章图片
- 我们从这个表引出next数组的值，next数组的值是除当前字符外的公共前后缀的长度，相当于将上表中数据向右移动一位，并且在前补充-1，得到如下
文章图片
- 接下来我们通过next数组来进行匹配推到，如下图流程：
- 第一步，i =0 ，j=0开始，当i = 2 ，j= 2 时候匹配失败，那么i不动，next[j]=next[2]=0,S右移j - next[j] = 2位 , j 回朔到 0
文章图片
- 第二次匹配，i= 2开始，j=0， 当匹配到i= 6 j=4 时候，失败，还是一样 i不动 ，j = next[j]=next[4] = 1,也就是S向右移 j-next[j]=3位
文章图片
- 第三次匹配，i = 6 ，j = 1 档i = 10， j = 5 时候匹配成功，返回 i-j=5
文章图片
- 当主串S 与模式串P 匹配失败时候，j = next[j],也就是P 右移动j-next[j]。
- 当模式串P后缀Pj-kPj-k+1…Pj-1与 主串S的Si-kSi-k+1…Si-1匹配成功，但是Pj，Sj j匹配失败时候，因为next[j] = k，相当于在不包含Pj的模式串中有最大长度为k的相同前后缀，也就是P0P1…Pk-1 = Pj-kPj-k+1…Pj-1
- 所以我们令j = next[j],让模式串 右移 j - next[j]位，使模式串 P0P1…Pk-1与主串。Si-kSi-k+1…Si-1对齐，让Pk 与Si 继续匹配，如下图所示：
文章图片
- 之前我们是通过推到的方式得到的next数组，当我们用代码实现时候，需要有一定的规则
- 当next[0] = -1,next[1] = 0这个容易得到
- 那么当通用情况，当j > 1 时候，如果我们已知next[j], 那么next[j+1]的值是我们需要求解的
- 有如下两种情况：
- 当Pk = Pj，next[j+1] = next[j] + 1 = k + 1,代表字符E 前面的模式串中有长度为k+1 的最长公共前后缀
文章图片
- 当Pk != Pj时候，说明p0p1…pk-1pk != pj-kpj-k+1…pj-1pj，这个时候ABC与ABD不相同，也就是E前面的模式串中没有长度为k+1的最大公共前后缀，所以next[j+1] = next[j] + 1 不在适用，我们需要寻找更短的最大公共前缀。
文章图片
- 因为next数组存储的是之前字符中最长公共前后缀，那么当我们pk ! = pj 的时候，我们需要找k之前的一个匹配，那么就说next[k] 的位置就是上图中的D，我们需要匹配的是 Pnext[k] = Pj 是否成立，也就让k = next[k] 然后在做比较。如果成立，那么next[j+1] = next[next[k]]+ 1，如果不成了，next[j+1] = 0
- 当Pk = Pj，next[j+1] = next[j] + 1 = k + 1,代表字符E 前面的模式串中有长度为k+1 的最长公共前后缀
- 如上步骤中我们找k 之前的位置next[k]处的前缀来判断是否有更短前缀，那为什么我们将k = next[k]就能找到最短前后缀，如下图中所示
文章图片
- 如上图，在Pk!=Pj时候，k = next[k] 用 Pnext[k] 去根Pj 匹配，
- 我们可以看到，Pj之前，有一段长度为k的已匹配串，在Pk之前也有一段蓝色的已匹配串，说明Pk字符前有一段长度为next[k] 的最大公共前后缀（蓝色标记）
- 如果Pk != Pj，说明P0P1…Pk-1Pk != Pj-kPj-k+1…Pj-1Pj,那么我们需要向前着更短的最大公共前后缀
- 因为此时Pk和Pnext[k] 前面的蓝色串已经完成了匹配
- 如果Pnext[k]能和Pj匹配，那么我们就找到了最大公共前后缀，否则我们需要再次向前找 Pnext[next[k]] 去根Pj继续匹配，直到找到更短的最大公共前后缀，或者字符串已经找到最开始位置，那么长度就是 0
- 经过如上分析有如下代码：
/**
* Created by jiamin5 on 2022/2/12.
* 给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回-1 。
* 来源：力扣（LeetCode第28题）
* 链接：https://leetcode-cn.com/problems/implement-strstr
*/
public class StrKmp {
public static void main(String[] args) {
System.out.println(strKmp("asdfuohadsuoufhuuowyqruoqiwhgbyur23iu4y2oi34hf", "uoq"));
}/**
*KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。
*KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。
*具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n)。
*
* */
public static int strKmp(String haystack, String needle){
if (needle == null && haystack == null) {
return 0;
}
if (haystack == null || haystack.length() <= 0) {
return -1;
}
if (needle.isEmpty()) {
return 0;
}
if (haystack.length() < needle.length()) {
return -1;
}
char[] hasChar = haystack.toCharArray();
char[] needChar = needle.toCharArray();
int [] next = getNext(needChar);
int i = 0, j = 0;
while (i参考文献
- 大佬v_JULY_v 的文章，比我更详细
- 上一篇：数据结构与算法–求1~n能组成的所有二叉搜索树的排列
- 下一篇：数据结构与算法–力扣108提将有序数组转换为二叉搜索树
推荐阅读
- 数据结构|索引的数据结构
- 【数据结构·水滴计划】|【数据结构】一篇文章带你彻底吃透·算法复杂度
- java|2018-2019-20172329 《Java软件结构与数据结构》第二周学习总结
- 程序员|Java技术篇！只需一篇文章吃透Java多线程技术
- JavaSE|Java入门了解
- JavaSE|JavaSE基本语法（下），你确定都懂了吗（）
- JavaSE|JavaSE基本语法（上），你确定都懂了吗（）
- Java练习|Java练习（三十五）---局部内部类访问方式练习
- JavaSE|Java数组解析（详解）