5000字详解KMP算法
目录
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;j<len;j++)
{
if(Sub[j]==Sub[next[j]])
k=next[next[j]];
}
}
}
KMP算法的具体代码实现(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<len;j++)
{
if(Sub[j]==Sub[next[j]])
k=next[next[j]];
}
}
}
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* next = (int*)malloc(sizeof(int) * lenSub);
Getnext(next, needle, lenSub);
while (i < lenStr && j < lenSub)
{
if (j==-1||haystack[i] == needle[j])//j==-1说明它回退到了起始位置,这是的j如果不++会//越界
{
i++;
j++;
}
else
{
j = next[j];
}
}
if (j >= lenSub)
{
free(next);//要释放开辟的内存
return i - j;
}
free(next);
return -1;
}