目录
KMP算法是什么?
暴力求解:
KMP算法原理:
建立next数组
代码实现next数组
next数组的优化
KMP算法的具体代码实现(C)
KMP算法是什么?
引自百度百科:
KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt提出的,因此人们称它为克努特—莫里斯—普拉特 *** 作(简称KMP算法)。KMP算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现,函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n)。
注 :此文的haystack代表的是主串,needle代表的是子串
暴力求解:暴力求解就是分别定义 两个指针 i 和 j 分别指向两个字符串的首字符,cur记录的是只一次比较的时候 i 的其实位置,所以,在上图中,当 i 和 j 指向的字符串不相同的时候,j 回到子串的起始位置,i 回到cur的位置后进行自增的运算,然后把 i 的位置赋值给cur,记录下这一次比较的起始为位置。所以此时的比较次数为两个字符串的长度的积,即m*n;
C实现具体代码
int strStr(char * haystack, char * needle){ if (!*needle) return 0; int lenStr = strlen(haystack); int lenSub = strlen(needle); if (lenStr < lenSub) return -1; int i = 0; int j = 0; int cur = i; while (i < lenStr && j < lenSub) { if (haystack[i] == needle[j]) { i++; j++; } else { i = ++cur; j = 0; } } if (j >= lenSub) return i - j; return -1; }KMP算法原理:
KMP算法不像暴力求解,当发现字符串不相等的时候,i 是不需要返回的,只需要 j 返回到某一个特定的位置,并从某一个位置直接开始比较,此时字符串比较的时间复杂度降为了O(m+n);
怎么确定 j 返回的具体位置呢?
定义 i 和 j 分别指向主串和子串的起始位置;当 i 和 j 指向第6个元素的时候,两个元素是不相等的,但是 指针 i 是不能进行返回 *** 作的,而 j 是返回到某一个特定的位置,怎么求 j 返回的位置?看下图:
很明显,当 i 和 j 能比较到第6个元素,说明前5个元素都是相同的,如果在子串中找到两个区间(区间a(从0到 x1 )能够和区间 b(从 x2 到 j-1))是相同的,那么主串中的一定存在一个区间c(从 x3 到 i-1)和区间 a 是相同的;在上图中;区间 a是[0,1],区间 b[3,4],区间 c是[3,4](主串中的)。 所以这个时候 j 应该回到子串中 ‘ 2 ’ 这个位置,即子串中的第三个元素' c '。
分析:因为主串和子串的前n-1个都是相同的,所以如果在子串中能够找到一对最长的相同前缀和后缀,则主串中存在一块相同区间大小的后缀就和子串的前缀是相同的,此时,子串中的‘ j ’只要回到前缀的后一位就行了。因为子串的前缀已经和主串的后缀的相同。在丄同中,‘ j ’将会到第三个元素后开始和‘ i ’指向的元素进行比较;如果还是不相同,就继续以刚才的方法进行返回,直到找到为止或者触发了结束条件。
现在,我们已经知道‘ j ’该返回到哪一个位置,但是,‘ j ’在子串的位置我们是不知道的,它可能在子串的第1/2/3/4/……n的位置,那我们该怎么确定‘ j ’的返回位置呢?
建立next数组为了确定‘ j ’在不同位置的返回值,我们建立一个next数组,将‘ j ’(j表示子串在某一个位置和主串的字符不能匹配)在不同位置时要返回到特定位置存放在数组中;给定一个子串(为了方便演示,该子串不同于之前的子串)
我们将next数组的第一个元素设为-1;而next[1]必为0;因为当字符串匹配到第二个元素不相同的时候,那么该元素前面只有一个元素(一个元素不构成相同的前缀和后缀);
当主串和子串匹配到第三个元素(‘ c ’)不相同时,该元素前面之后元素‘ a ’和‘ b ’,不存在相同的前后缀,所以next[2]=0;
当主串和子串匹配到第四个元素(‘ a ’)不相同时,‘ a ’,‘ b ’,‘ c ’,也够不成相同的前后缀;所以next[3]=0;
当主串和子串匹配到第五个元素(‘ b ’)不相同时,此时前四个元素‘ a ’,' b ',' c ',' a '中,存在前缀‘ a ’和后缀‘ a ’构成相同的前后缀,前后缀的长度为1,那么此时next[j]=1;
同样的,当主串和子串匹配到第八个元素(‘ d ’)不相同时,此时存在前缀“abca”和后缀“abca”是相同的(这里的前缀后缀共用了一个‘ a ’,这种情况相对比较特殊,但也算);此时next[7]=4;
当主串和子串匹配到第九个元素(‘ a ’)不相同时;不存在区间a(0到x1)和区间b(x2到 j-1,此时的 j==8);所以next[8]=0;
为了鉴别自己是否掌握next数组的建立;请完成下面的一个小测试
给定子串,求其next数组
答案:(如果还是不会,请仔细推敲前面构建next数组的过程)3
既然我们解决如何构建next数组,那我们可以走下下一步------->>>代码实现next数组
代码实现next数组以下图的子串为例 :
3
我们先来做一个假设:next[ j-1 ]==k;
next[ j ]==k说明在字串中存在区间a(0到k-1)和区间b(x到 j-1);肯定会有好兄弟问为什么是k-1;因为next[ j-1 ]==k,则说明在子串中存在一对相同的前后缀,长度为k,而0又是第一个元素,所以为k-1;
因为前后缀向同,则 j-1-x=k-1-0------>>>>x=j-k;
所以存在区间a(0到 k-1)和区间b( j-k 到 j-1)是相同的
即: needle[0]……needle[k-1]==needle[j-k]……needle[j-1],两边的长度均为K;
如果此时存在needle[ j ]==needle[ k ];
那么存在: needle[0]……needle[k-1] needle[ k ]==needle[j-k]……needle[j-1] needle[ k ]; 此时前后缀的长度为k+1;
如果此时needle[ j ] !=needle[ k ];
当指针‘ j ’指向第八个元素的时候,此时k==4,needle[ 7 ] != needle[ 4 ];此时的不存在一对前后缀是相同的;那么,就要跳过前一个元素的后缀取找相同的前后缀(前一个元素是d(下标 7),他的后缀为“abca”);所以将next[k]赋值给 k(此时k==4),然后比较此时的next[ k ]和needle[ j ];如果相等,将次时代 k +1,如果不相等,继续将next[ k ] 赋值为 k;(此时k==1); 而needle[ k ]任然不等于needle [ j ];继续将next[ k ]赋值给k(此时k==-1);说明不存在相同的前缀,则进行 k+1 *** 作得到k==0;
将上述过程用代码实现
void Getnext(int* next, char* needle, int len) { if (len == 1) { next[0] = -1;//如果子串只有一个元素 } else { next[0] = -1; next[1] = 0; int i = 2; int k = 0;//表示next的第i-1项k=next[i-1],此时的i为2;即你next[1]==0; while (i < len) { if (k == -1 || Sub[i - 1] == needle[k])//k==-1说明没有了相同的前后缀了 { next[i] = k + 1; i++; k = next[i-1];//因为此时的 i 变了,k 也要跟着变; } else { k = next[k];// } } }next数组的优化
来看下面的一个子串:
当字符串匹配到不相同的时候,要进行 j =next [ j ]的 *** 作(即将 j 返回到某一位置);
如果此时存在 needle [ j ]==needle[ next[ j ] ];说明如果会退到的位置和当前的字符一样,那么next在当前的位置处的值和needle[ next[ j ] ]位置的next值一样。
优化后的代码
void Getnext(int* next, char* Sub, int len) { if (len == 1) { next[0] = -1; } else { next[0] = -1; next[1] = 0; int i = 2; int k = 0;//表示next的第i-1项k=next[i-1],此时的i为2;即你next[1]==0; while (i < len) { if (k == -1 || Sub[i - 1] == Sub[k]) { next[i] = k + 1; i++; k = next[i-1]; } else { k = next[k]; } } //优化next数组 for(int j=1;jKMP算法的具体代码实现(C) void Getnext(int* next, char* Sub, int len) { if (len == 1) { next[0] = -1; } else { next[0] = -1; next[1] = 0; int i = 2; int k = 0;//表示next的第i-1项k=next[i-1],此时的i为2;即你next[1]==0; while (i < len) { if (k == -1 || Sub[i - 1] == Sub[k]) { next[i] = k + 1; i++; k = next[i-1]; } else { k = next[k]; } } //优化next数组 for(int j=1;j= lenSub) { free(next);//要释放开辟的内存 return i - j; } free(next); return -1; } 欢迎分享,转载请注明来源:内存溢出
评论列表(0条)