这篇文章是建立在上篇文章的基础上的,看此篇文章要有串的基本知识
举个例子引进我们今天的知识
假设我们这里有两个字符串,一个主串,一个子串
主串: aaa223aa225
子串: aa22
我们这里需要进行匹配,传统的朴素模式匹配算法,就是主串下标i从1开始,主串j从1开始,i和j相同即访问下一个字符,不同则i跳到下一个,j从1开始
我们在第一轮第三个未匹配上,未必要让两个字符串下标或者是指针都回溯,只需要让模式串指针回溯即可,比如第三个不同,但是主串第二个到第四个全是子串的后缀,这个时候我们可以回溯到第三个，在对上述字符串进行匹配，如果匹配到了，就继续，没有匹配到就继续回溯我们的模式串指针。
以下是我对两者知识的介绍(以下文章的SString皆是引用了这个)
struct SString {
char date[MAX_SIZE];
int length;
};1.朴素模式匹配算法
其实就是从第一个位置一个一个往下匹配，没有任何优化，在最好的情况下时间复杂度为O(m)，最坏的时间复杂度为O(n*m)O((n-m+1)*m)。最好的第一个位置就是子串,最坏的没有子串
//在主串里面查找模式串
int index(SString a, SString b) {
int i, j = 1;
while (i <= length(a) && j <= length(b)) {
if (a.date[i] == b.date[j]) {//从头开始匹配,相同则继续
i++;
j++;
}
else {
i = i - j + 2;//不同则,模式串从下一位开始,子串从头开始
j = 1;
}
}
if (j > length(b))return i-length(b);//如果子串指针j超过子串的长度,说明这个位置有一个子串
else return 0;
}2.KMP算法
先对子串t进行next判断，得到一个next数组，再进行比较。时间复杂度为O(n+m)
KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n)。
我们的next()数组就是前缀表,作用就是用来找最长相等前后缀
前后缀简单介绍
前缀：必须包含第一个字母但不包含最后一个字母的连续子串
后缀：必须包含最后一个字母但不包含第一个字母的连续子串前缀表:最长相等前后缀
KMP代码实现
这里推荐看哔哩哔哩这个视频KMP算法之求next数组代码讲解_哔哩哔哩_bilibili,讲解next数组球阀比较好!!
举个例子说明一下
(这是我通过deepseek替大家模拟的过程,如果不懂,可以去deepseek以这个样例测试一下)
以模式串 b = "ababaa" 为例，模拟修正后的代码执行过程
这是求next数组的操作
i<=lenth可以会导致数组越界,记得把数组开大些(一两位足以),这个基本上没有什么问题
void getnext2(char ch[], int length, int next[]) {
next[1] = 0; // 初始化 next[1]
int i = 1, j = 0;
while (i <= length) { // 修改为 i < length，避免越界
if (j == 0 || ch[i] == ch[j]) {
i++;
j++;
next[i] = j; // 更新 next[i]
} else {
j = next[j]; // 回溯
}
}
}我们以模式串 b = "ababaa" 为例，详细模拟 getnextval 函数的执行过程，并生成 nextval[] 数组。
这是求nextval数组的操作
(这是根据next数组求nextval的方法)下面还有直接求nextval数组的方法
void getnextval(char b[], int length, int next[], int nextval[]) {
nextval[1] = 0;
for (int j = 2; j <= length; j++) {
if (b[j] == b[next[j]]) {
nextval[j] = nextval[next[j]];
} else {
nextval[j] = next[j];
}
}
}直接求nextval数组
void getnextval(char ch[], int length, int nextval[]) {
nextval[1] = 0;
int i = 1,j = 0;
while (i <= length) {
if (j == 0 || ch[i] == ch[j]) {
i++, j++;
if (ch[i] == ch[j]) {
nextval[i] = nextval[j];
}
else nextval[i] = j;
}
else {
j = nextval[j];
}
}
}这是具体的KMP具体操作
next[]数组实现
int index_KMP(SString a, SString b) {
int i = 1, j = 1;
while (i <= length(a) && j <= length(b)) {
if (j == 0 || a.date[i] == b.date[j]) {
i++, j++;
}
else {
j = next2[j];
}
}
if (j > length(b))return i - length(b);
return 0;
}nextval[]数组实现
int index_KMP(SString a, SString b, int nextval[]) {
int i = 1, j = 1;
while (i <= length(a) && j <= length(b)) {
if (j == 0 || a.date[i] == b.date[j]) {
i++, j++;
} else {
j = nextval[j];
}
}
if (j > length(b)) return i - length(b);
return 0;
}您觉得此篇还行,请留下你的点赞,谢谢大佬!!!
