写这篇文章,真的花了我很多功夫,希望能够对看到的大家有所帮助啦
可以重点只看下面标出的关键点,即可快速掌握KMP算法
目录
KMP算法的作用
首先,KMP算法的作用是进行模式串的匹配
也就是对于一个已知的长字符串t,我们在其中找到,与模式串m完全相同的部分,并且返回相同部分的首数组标号
采用BF算法,能够非常直观求出匹配位置,但是由于指针回溯,进行了多余的比较,非常缓慢
这样就有了KMP算法的诞生
下文中,我们将待比较的字符串,存入下面这样的结构体中:
typedef struct Str
{
char *ch;
int length;
} Str;
next数组是什么+用KMP返回首次匹配位置
我们发现,可以减少BF算法比较次数的原因在于,BF算法中,每一次模式串的指针回移太长了
我们发现将如下图的指针i和j全部回移,归位,就会多进行很多无用的比较
我们之所以知道多余的回退是没有用的,是由模式串本身的特性决定的
我们已知,即使在出现不匹配时,不匹配处的左侧的字符串和主串对应位置,是相同,或者说匹配的.
就像上图中一样,进行到第三步的时候(图中标错了),前面的"ana"在主串和模式串中,都是相同的
我们可以考虑引入一个概念,也就是"最大公共前后缀",假设其位数为n位
也就是从该部分匹配串的第一位开始往后数n位,和此部分匹配串的最后一位开始往前数n位,两者完全相同
当然也会有"次大公共前后缀",但是如果是次大的话,就会出现回移过少,漏掉了可能性的情况
我们必须考虑最大的公共前后缀,让j指针回移最多,并且不会漏掉可能性,从而最大程度得节约步骤和考虑全面.这样一个最佳位置,其实就是最大公共前后缀的位数.
使用KMP的过程中,我们不回移i指针,仅仅将j指针回移到左边的"部分匹配串"的"最大公共前后缀"中的前缀的后一位的位置,重新继续与主串匹配
我们的next数组,与模式串的长度相同
其中,记录的就是当前位置左边的"部分匹配串"的最大公共子串长度n
也是j指针接下来要移动到的位置,在下图中已经说明了.
下面的代码是用上图中的第二种编号方法写出的:
int KMP(Str t, Str m)
{
int next[m.length];
getNext(m, next);
int i = 0, j = 0;
//循环体的条件是模式串和主串都没有遍历完成
while (i < t.length && j < m.length)
{
//如果当前匹配成功,则主串和模式串均右移
//特殊情况下,模式串指针指向-1,主串和模式串也都要后移
if (j == -1 || t.ch[i] == m.ch[j])
i++, j++;
//如果没有匹配成功,则仅模式串回移到next数组中记录的最佳位置
else
j = next[j];
}
if (j == m.length)
return i - j + 1; //这里返回的是主串的第几个开始成功匹配上
// return i - j; //如果去掉+1则是表示开始匹配位置的数组标号
else
return -1; //没有匹配成功则返回-1
}
next数组
void getNext(Str m, int next[]) //函数传参不允许引用数组
{
int i = 0, j = -1;
next[0] = -1;
while (i < m.length - 1)
{
if (j == -1 || m.ch[i] == m.ch[j])
next[++i] = next[++j] + 1;
else
{
j = next[j];
}
}
}
next数组改进为nextval数组
为什么要引入nextval数组呢?
其实上文中认为next数组就是模式串回退的最佳位置,其实是不对的
next数组中保存的是"当前位置左边部分匹配串"的"最大公共前后缀"的位数n或者是n-1(没有本质差别)
虽然next数组能用,它确实大大优化了模式串的后移位数,并且不会遗漏正确结果,但是它仍不是,效率最高的后移位置
为什么nextval数组更加优化了?
关键点!!!--具体做题和实操照这个做就够了,上面的原理看个大概就够了,这个例子则要反复熟悉,并且自己再多出几个题目反复练习验证,达到熟练
nextval数组是怎样得到的?
是在已知next数组的基础上,进行如下规则的判断得到的:
求next和nextval数组的例子如下,可以跟着线条多画几遍,就能够熟练了:
就拿eg2中数据为例,在模式串为0位置处,next和nextval数组的值都必然是-1,这是默认不变的
- 首先,求next数组的方法就是:
首先以位置5为例:
要求出位置5的next值,必须要看位置5-1(=4)的next值
比较位置4的字符和next [ 4 ] (=1)位置的字符,如果相等,则5位置存入next[4]+1
若不等,则比较位置4字符和next [ next [ 4 ] ] (=0)的字符,如果相等,则存入next [ next [ 4 ] ] +1(=1)
然后,以位置7为例,考虑一种特殊情况,也就是到了最后也没有匹配成功的情况:
求7看6,'b'为标准,向前找到2号c,不匹配
再向前找到0号'a',仍然不匹配,则直接返回(-1+1)=0
总结一下求next值方法!!!
前位字符为标准,next值作模串标号向前跳,匹配则返回该标号加1,不匹配继续向前跳,0号还不匹配直接返回0
- 在next数组的基础上,求nextval的方法就是:
以位置8为例:
求nextval数组,直接以当前位置的next值作为标号,向前跳一位,比较当前位和前跳位字符
1.匹配,则当前位nextval值,等于前跳位nextval值
2.不匹配,则当前为nextval值,直接等于当前位next值
总结一下求nextval值方法!!!
当前位字符为标准,next值为模串标号向前跳一位,匹配nextval值等于前跳位,不匹配当前位next值直接落下来
void getNextval(Str m, int nextval[])
{
int i = 0, j = -1;
int next[m.length];
next[0] = -1;
nextval[0] = -1;
while (i < m.length - 1)
{
if (j == -1 || m.ch[i] == m.ch[j])
{
next[++i] = ++j;
if (m.ch[i] == m.ch[next[i]])
nextval[i] = nextval[next[i]];
else
nextval[i] = next[i];
}
else
j = next[j];
}
}
用KMP求出所有匹配位置
将匹配起始点结果存入P数组中
可以灵活根据需要,修改这段代码,可以参考以下例子:
https://blog.nowcoder.net/n/2dc728211ba84e8096a41196ee5c6506
调整之后,就能够存入符合特定要求的匹配串了
void KMP_Multi(Str t, Str m, int P[])
{
int nextval[m.length];
getNextval(m, nextval);
int i = 0, j = 0;
int R = 0;
while (1)
{
while (i < t.length && j < m.length)
{
if (j == -1 || t.ch[i] == m.ch[j])
i++, j++;
else
j = nextval[j];
}
if (j == m.length)
{
P[R++] = i - j;
// ver1以下是从后续开始,不找包含重复的部分
// /*
i = i - j + m.length;
j = 0;
// */
// ver2以下是找出所有的重复部分
/*
i = i - j + 1;
j = 0;
*/
}
else
{
P[R] = -1;
break;
}
}
}
代码的完整实现
关键点!!!--getNextval和KMP_Multi这两个函数,可以直接拿来,经过简单的修改,就能用于绝大多数的情况,如果能够做到完全理解并且默写,则KMP算法就算完全掌握了
#include "stdio.h"
typedef struct Str
{
char *ch;
int length;
} Str;
void getNextval(Str m, int nextval[])
{
int i = 0, j = -1;
int next[m.length];
next[0] = -1;
nextval[0] = -1;
while (i < m.length - 1)
{
if (j == -1 || m.ch[i] == m.ch[j])
{
next[++i] = ++j;
if (m.ch[i] == m.ch[next[i]])
nextval[i] = nextval[next[i]];
else
nextval[i] = next[i];
}
else
j = next[j];
}
}
void KMP_Multi(Str t, Str m, int P[])
{
int nextval[m.length];
getNextval(m, nextval);
int i = 0, j = 0;
int R = 0;
while (1)
{
while (i < t.length && j < m.length)
{
if (j == -1 || t.ch[i] == m.ch[j])
i++, j++;
else
j = nextval[j];
}
if (j == m.length)
{
P[R++] = i - j;
// ver1以下是从后续开始,不找包含重复的部分
// /*
i = i - j + m.length;
j = 0;
// */
// ver2以下是找出所有的重复部分
/*
i = i - j + 1;
j = 0;
*/
}
else
{
P[R] = -1;
break;
}
}
}
int main()
{
Str m = {.ch = "anan\0", .length = 4};
Str t = {.ch = "baanananaanan\0", .length = 13};
int nextval[m.length];
getNextval(m, nextval);
printf("nextval数组如下:\n");
for (int i = 0; i < m.length; i++)
printf("%d\t", nextval[i]);
printf("\n");
int P[100] = {0};
KMP_Multi(t, m, P);
printf("匹配成功的位置,记录如下:\n");
int i;
for (i = 0; P[i] != -1; i++)
printf("%d\t", P[i]);
printf("%d\n", -1);
return 0;
}
/*
nextval数组如下:
-1 0 -1 0
匹配成功的位置,记录如下:
2 9 -1
*/
京公网安备 11010502036488号