关键词：
活动地址：CSDN21天学习挑战赛
怕什么真理无穷，进一步有一份的欢喜。
目录
【21天学习挑战赛】KMP模式匹配算法
✌我为什么参与挑战赛
1，机缘
读到研一了，暑假假期打开私信发现这个挑战赛就鼓起勇气参加了。
2，期待的收获
A, 本人在华南理工大学攻读专硕，目前研究方向是图像恢复，从事深度学习相关工作，目标是从事Java后端开发。
B, 期待您的反馈，如果有什么不对的地方，欢迎指正！
C, 期待认识志同道合的领域同行或技术交流。
如果感觉博主的文章还不错的话，还请👍关注、点赞、收藏三连支持👍一下博主哦
🍉模式匹配算法？
对于子串的定位操作通常成为串的模式匹配,可以看下图就是匹配的过程
💬KMP模式匹配算法的定义
可以看到上面的匹配是一位一位的挪动，匹配算法很低效，KMP算法是前人发表的一种模式匹配算法来大大避免重复遍历的情况。
✨KMP模式匹配算法的优劣
优势
大大减低时间复杂度，从原来的O((n-m+1)*m)降低为O(n+m)
劣势
原理较复杂，实现困难
🍵KMP模式匹配算法的步骤
- 构建next数组(请参考KMP学习资料)
- 进行匹配
✍️ 算法实现
package wpc.leetbook.arrString;
import org.junit.jupiter.api.Test;
import java.util.Arrays;
public class KMP
private int[] get_next(String T)
int m = T.length();
int[] next = new int[m];
next[0] = -1;
int j = -1, i = 0;
// j表示当前字符之前的串的前后缀的相似度
while (i < m - 1)
// T[j] 表示前缀的单个字符
// T[i] 表示后缀的单个字符
if (j < 0 || T.charAt(j) == T.charAt(i))
j++;
i++;
next[i] = j;
else
//如果字符不同就进行回溯，退到合适位置，i不变
j = next[j];
return next;
public int strStr(String haystack, String needle)
if (needle.length() == 0) return 0;
int m = haystack.length(), i = 0;
int n = needle.length(), j = 0;
//获取next数组
int[] next = get_next(needle);
while (i < m && j < n)
//两个字母相等，继续匹配
if (j < 0 || haystack.charAt(i) == needle.charAt(j))
i++;
j++;
else
//j退到合适位置，i不变
j = next[j];
if (j == n)
return i - j;
else return -1;
@Test
public void test()
int[] arr = get_next("abcabx");
System.out.println(Arrays.toString(arr));
如果觉得对你有帮助的话:
👍 点赞，你的认可是我创作的动力！
⭐️ 收藏，你的青睐是我努力的方向！
✏️ 评论，你的意见是我进步的财富！
模式匹配----kmp算法(代码片段)
...，心却为她打着伞、在上篇中，我们讲到了BF暴力模式匹配算法。下面我们将讲述BF算法的优化版本算法KMP算法。🎃KMP定义我们知道BF算法效率低的原因就是要回溯，即在匹配失败后，子串回溯到0，主串回... 查看详情
kmp算法(代码片段)
...法）。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n)。原理匹配模式... 查看详情
21天学习挑战赛—python学习记录第一篇(代码片段)
21天学习挑战赛—Python学习记录第一篇——活动地址：CSDN21天学习挑战赛————前言一名大学牲，参与本次21天学习挑战赛，一个是为了充实自己的暑假，不在暑假过度放松，第二个就是想要去学会python这... 查看详情
21天学习挑战赛—python学习记录第一篇(代码片段)
21天学习挑战赛—Python学习记录第一篇——活动地址：CSDN21天学习挑战赛————前言一名大学牲，参与本次21天学习挑战赛，一个是为了充实自己的暑假，不在暑假过度放松，第二个就是想要去学会python这... 查看详情
串的模式匹配算法之kmp(代码片段)
title:串的模式匹配算法之kmptags:数据结构与算法之美author:辰砂1.引言首先我们需要了解串的模式算法目的：确定主串中所含子串第一次出现的位置（定位）；常见的算法种类：BF算法（又称古典的、经典的、朴素的、穷举的），KM... 查看详情
算法学习——kmp字符串匹配算法(代码片段)
KMP算法是一种非常高效和常用的算法。其核心就是通过预处理一个寻找公共最大前后缀的Next[]数组，减少匹配失败时的重复无效匹配。next数组本质：next[i]=j表示下标以i-j为起点，i为终点的后缀和下标以0为起点，j为终点的前缀... 查看详情
第四章学习小结(代码片段)
...学BF算法时就在想如何改进可以使匹配更加简便后来KMP的学习让我对串的学习有了更深入的了解同时BF和KMP算法之间的联系也是一个算法改进的很好学习范例 7-1串的模式匹配给定一个主串S（长度<=10^6）和一个模式T（长度<... 查看详情
21天学习挑战赛python学习第四篇：多线程threading模块(代码片段)
【21天学习挑战赛】Python学习第四篇：多线程threading模块——活动地址：CSDN21天学习挑战赛——多线程的理解就是两件或两件以上的事情通过代码同时发生。而一般情况下我们写python代码的话是从上往下执行的，有... 查看详情
21天学习挑战赛python学习第三篇：os标准库(代码片段)
【21天学习挑战赛】Python学习第三篇：os标准库活动地址：CSDN21天学习挑战赛——介绍os模块提供了多数操作系统的功能接口函数。当os模块被导入后，它会自适应于不同的操作系统平台，根据不同的平台进行... 查看详情
单模式串匹配----浅谈kmp算法(代码片段)
模式串匹配，顾名思义，就是看一个串是否在另一个串中出现，出现了几次，在哪个位置出现； p.s. 模式串是前者，并且，我们称后一个(也就是被匹配的串）为文本串； 在这篇博客的代码里，s1均为文本串，s2均为模... 查看详情
kmp算法详解及其java实现(代码片段)
...法，又称作“看猫片”算法（误），是一种改进的字符串模式匹配算法，可以在O(n+m)的时间复杂度以内完成字符串的匹配操作，其核心思想在于：当一趟匹配过程中出现字符不匹配时，不需要回溯主串的指针，而是利用已经得到... 查看详情
串串的模式匹配算法（子串查找）bf算法kmp算法(代码片段)
串的定长顺序存储#defineMAXSTRLEN255,//超出这个长度则超出部分被舍去，称为截断串的模式匹配：串的定义：0个或多个字符组成的有限序列S=‘a1a2a3…….an‘n=0时为空串串的顺序存储结构：字符数组，串的长度就是数组末尾‘ 查看详情
字符串模式匹配中的bf算法与kmp算法(代码片段)
博客园的编辑器太难用了。。。。。。。。。。。BF算法即暴力算法，很简单，随便举个栗子：#include<iostream>#include<cstring>usingnamespacestd;//S[]:要匹配的链//T[]:模式串intBFsearch(intstart,charS[],charT[])intslen=strlen(S);inttlen=strlen(T 查看详情
改进kmp模式匹配算法(代码片段)
看了算法的大致步骤，然后自己一一证明了每一步的正确性，注释里写了一些理解。这也不是新鲜的做法，只是感觉这个程序非常精巧，反复地使用数学归纳法。让我感觉很新鲜。1/*2next[i]存放：match[i]处失配,orig在对应位置将要... 查看详情
kmp算法(代码片段)
...设现在我们面临这样一个问题：有一个文本串S，和一个模式串P，现在要查找P在S中的位置，怎么查找呢？ 如果用暴力匹配的思路，并假设现在文本串S匹配到i位置，模式串P匹配到j位置，则有：如果当前字符匹配成功（... 查看详情
数据结构第四章学习心得(代码片段)
一.本章内容小结本章我们学习了串，数组和广义表首先，我们学习了串，线性表主要由顺序表示或链式表示。在实际应用中，常以栈，队列，字符串等特殊形式使用。线性表和串的操作基本类似，但串的操作针对串的整体，而... 查看详情
kmp算法(代码片段)
数据结构_串对于串,今天就总结了一个算法,关于字符串的模式匹配问题(重点在于kmp算法).普通的模式匹配算法,当匹配不成功时需要将主串的下标恢复到之前匹配的下一个字符,子串下标置为串首;而kmp算法则不需要重置主串的下标... 查看详情
数据结构串---kmp模式匹配算法实现及优化(代码片段)
KMP算法实现#define_CRT_SECURE_NO_WARNINGS#include<stdio.h>#include<stdlib.h>#include<string.h>#defineOK1#defineERROR0#defineTRUE1#defineFALSE0#defineMAXSIZE40typedefintElemType;typedefin 查看详情