前言:
而今咱们对“串的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怎么求