龙空技术网

1个公式就弄懂了KMP模式匹配算法,困扰我多年的问题终于解决了

师兄睿谈 647

前言:

而今咱们对“串的kmp算法”大约比较注重,各位老铁们都需要知道一些“串的kmp算法”的相关知识。那么小编在网摘上网罗了一些对于“串的kmp算法””的相关资讯,希望小伙伴们能喜欢,我们快快来学习一下吧!

KMP算法可以说是一个很经典的模式匹配算法了,它一种改进的字符串匹配算法,但很多人就是不理解,甚至多看几次之后也没有理解透彻。

我们要查找S字符串串中是否包含P字符串,将P串称之为模式匹配串(以下简称模式串)。

朴素模式串匹配算法

我们先用一个动图来看不用KMP匹配的 朴素模式串匹配算法:

浅显易懂吧!但是呢,朴素的模式串匹配算法是有效率问题的!比如像下面这种:

在匹配到第5个字符时,发生了P串和S串不匹配的情形,然后按照朴素的算法,需要回溯 i 指针到 1 位置,回溯 j 指针到 0 位置,然后我们依次移动P串进行匹配计算:

在i = 3时,此时后面就有S[3] = P[0], S[4] = P[1], S[5] = P[2]:

然后S[6] != P[3]:

才发现又是不匹配的,其中我们可以用肉眼观察到,当S[1]和P[0]发生不匹配时,P串依次的从S串第1个位置,第2个位置进行比较,只有到S串第3个位置字符是A时才和P串的第0个字符匹配,而且后面的两个字符也能够匹配,但是,S串第5个字符是不匹配的。

假如我们是通过肉眼判断的话,当

这时不匹配时,我们应该直接移动 j 到

进行匹配判断,因此,朴素的模式匹配是有一部分匹配判断是多余的,我们要想办法把它优化,在S[5] != P[5] 时,直接进行判断 S[5] 是否等于 P[2]。这是因为P[0] == P[3], P[1] == P[4];P串前后有相同的子串,可以看下图知道:

由于S[3] = P[3], S[4] = P[4],而 P串前后有相同的子串:P[0] == P[3], P[1] == P[4],因此,我们可以直接进行判断S[5] 是否 等于 P[2]。也就是说当S[i] 和 P[j] 不匹配时,我们可以决定 j 的下一个位置是什么,从而使 i 指针不产生回溯。

推广到一般情况,我们可以用数学来证明这个事情:

这就有了KMP算法,我们假设S串下标是i,P串下标是 j。当P串中存在重合的子串时,我们需要分析出j指针指向的下一个位置,为了记录所有 j 取值的情况,用next数组来记录每一个P串的字符不匹配时需要将 j 指针移动到的位置下标。

KMP算法核心

核心思想:模式串中有重合的子串,那么当模式串p[j]匹配失败时,要移动到下标为k的位置进行匹配,k需要满足:0 ~ k 之间的 k+1 个字符与 j-1-k ~ j-1 之间的 k+1 个字符相同。next数组用于存放匹配失败时,next[j]代表需要进行匹配下一个字符的位置p[next[j]]。

可以用数学语言表述为:

模式串p中有n个字符,其中

如果存在

使得

那么令

否则(p中没有字符相同),令

说明:

当 k = 0 时,表示模式串p中前后只有一个字符能够重合,此时要从p[0](从头开始)匹配;当 k = -1 时,表示模式串中没有可以前后重合的部分子串,此时需要将原始串的指针下标(i)后移。

记住:k = next[j]; 当 s[i] != p[j]时,需要将j指针移动到p串的k下标位置,那么next[j]就用来存储这个k。

具体解释:

第一种情况:j == 0时,s[i]和p[j]不匹配,那j指针不可能再向左移动了,此时应该要i指针向后移动。这种情况,记next[j] = -1;第二种情况:j == 1时, s[i]和p[j]不匹配,那j指针显然是要移动到0位置的。这种情况,记next[j] = 0;第三种情况:p[j] = p[k] 时,有 next[j+1] = next[j] + 1;

证明:

因为p[j]之前有 p[j-k ~ j-1] = p[0 ~ k-1]; 所以 next[j] = k;

那此时有 p[j] = p[k];可以得到 p[j-k ~ j-1] + p[j] == p[0 ~ k-1] + p[k];

即:p[j-k ~ j] == p[0 ~ k];

那么 next[j+1] = k + 1 = next[j] + 1;

第四种情况:p[j] != p[k] 时,此时应该是 k = next[k];

代码中为了保证循环依次计算j之前的重合子串,用j+1表示当前匹配不成功的字符位置,则计算next数组的算法如下:

void getNext(char *p, int next[]){    int j = 0, k = -1, len = strlen(p);    if (len == 0)    return;    next[0] = -1;    while (j < len-1)    {        if (k == -1 || p[j] == p[k])            next[++j] = ++k; //next[j+1]记录p[j+1]匹配失败时需要跳转的位置        else            k = next[k];    }}

由此可以写出KMP算法:

int KMP(char s[], char p[]){    int[] next = getNext(p);    int i = 0, j = 0;    while (s[i] && p[j])    {        if (j == -1 || s[i] == p[j])            i++, j++;        else        j = next[j]; // j回到指定位置    }    if (p[j])        return -1;    return i - j;}
改进的KMP算法

回顾第三种情况:p[j] = p[k] 时,有 next[j+1] = next[j] + 1;

当s[i] != p[j]时,需要将 j 移动到 next[j],然而由于 p[j] == p[next[j]],导致移动j之后 s[i] 和 p[next[j]]仍然不匹配,此时需要继续将j移动到next[next[j]]进行比较;

显然,当p[j] 与 s[i]不匹配时,若p[j] == p[next[j]],就可以跳过j移动到next[j]这一步,直接进行移动到下一步。

因此,修正后的nextval数组如下:

改进思想:

在保证

p[i] = p[j - k + i],(i = 0, 1, ..., k)

后,再继续检查 p[j] 是否与 p[k] 相等?(此时原本是令 next[j] = k)

因为此时 k 记录的是 p[j] 发生不匹配时,需要直接跳到下次比较的位置;

所以:

如果 p[k] = p[j] ,则同样发生不匹配,这时应该令 next[j] = next[k](因为 p[k] 与 p[j] 相同,则当前字符 p[j] 不匹配时,p[k]同样也不匹配,next[k]记录的是 p[k] 不匹配时需要跳转的位置,因此 p[j] 不匹配应该直接跳转到 next[k] 位置进行比较);如果 p[k] != p[j],那么当 p[j] 不匹配时才应该跳转到 p[k] 再次进行匹配,此时应令 next[j] = k。

改进算法如下:

void getNextval(char p[], int nextval[]){    int j = 0, k = -1, len = strlen(p);    if (len == 0)        return;    nextval[j] = k;    while (j < len-1)    {        if (k == -1 || p[j] == p[k])        {            ++j, ++k;            if(p[j] != p[k])                nextval[j] = k;            else            nextval[j] = nextval[k];        }        else            k = nextval[k];    }}

kmp匹配的算法代码如下:

/*** kmp模式匹配子串* 参数:* *str - 源串* *substr - 目标串*/int kmp(char *str, char *substr){    int i=0, j=0, slen = strlen(str), plen = strlen(substr);    int *nextval = (int *) calloc(plen, sizeof(int));    getNextval(substr, nextval);    while(i < slen && j < plen)    {        if( j == -1 || str[i] == substr[j])            i++, j++;        else            j = nextval[j];    }    if(j == plen)        return i - j;    else        return 0;}

如果觉得这篇文章对你有帮助,就帮我点赞并转发吧!我会持续分享IT、科技、技术方面的知识、经验,如果你喜欢的话,可以加个关注收藏一下吧!@IT研究僧大师兄

标签: #串的kmp算法 #c语言实现kmp算法 #kmp算法next视频 #kmp算法中next0 #kmp算法中nextval怎么求