我所理解的KMP算法以及改进

最近在复习数据结构，看到KMP算法这里，花了好久才搞懂，下面总结一下我的一些理解。

先来看问题：

串的模式匹配：返回子串T在主串S中的位置，若不存在则返回-1

常规的匹配方法是，用i、j分别指示两个字符串，从主串S（假设长度为n）的第1个字符开始，和子串T（长度为m）的第1个字符进行比较，如果一样，i、j都加1，继续比较下一个；不一样，选取S第i-j+2个字符，再和子串的第1个字符重新开始比较，直到S的末尾或者子串T在S中被找到。
这样的时间复杂度是O(n*m)。

下面介绍：KMP算法

该算法是D.E.Knuth、J.H.Morris和V.R.Pratt同时发现的，因此被称为KMP算法，此算法可以在O(m+n)的时间数量级上完成串的模式匹配操作。

常规的算法是 i 回退到起始位置的下一字符开始匹配，而KMP算法则根据子串T本身的性质，利用已经匹配的结果，将模式（子串T）尽可能地往后“滑”。而“滑”多远就要根据数组next来判断。

该怎么理解next数组呢？

举个例子： 若子串为"ababaca"，next数组长度为7
首先next[0] = -1，next[k] (1≤k≤6)表示前k个字符前缀和后缀相同的最大长度

注意这里前缀指的是从第一个字符开始，到第k个字符结束，如"aaaa"对应next[3]长度为3

上面的子串的前k个字符分别对应下表

因此，next[7] = [-1,0,0,1,2,3,0]，这就是求next数组的步骤。

上代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void get_next(string T, int next[])
{
unsigned int j=0;
int k=-1;
next[0] = -1;
while(j < T.length()-1)
//O(m)
{
if(k==-1 || T[j]==T[k])
{
j++;
k++;
next[j] = k;
//next[++j] = ++k;
}
else
k = next[k];
}
}

下面我们看看此程序的运行过程，还是子串"ababaca"

其实你像这样过一遍就理解这个函数了，不得不说实在是巧妙！

下面是KMP函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int KMP(string S, string T, int next[])
{
unsigned int i=0,j=0;
while(i<S.length() && j<T.length())
//O(n)
(n>m)
{
if(j==-1 || S[i]==T[j])
{
//j=-1时，没有匹配的，i++，j=0，从子串第一位开始重新匹配
i++;
j++;
}
else
j = next[j];
}
if(j==T.length())
return i-j;
else
return -1;
}

总的时间复杂度就是get_next()的O(m)加上KMP()的O(n)。

最后说下上面算法的缺陷（其实不能算是缺陷，只是还可以做到更快）：

对于子串T= "abab"，上边的算法得到的next数组应该是[ -1，0，0，1 ]

若主串S= "abadab"，程序执行到S[3]和T[3]处，不匹配，因此j=next[3]=1，而S[3]和T[1]还是不匹配，但这一步是完全没有意义的。因为对于子串S，后面的'b'已经不匹配了，那前面的'b'也一定是不匹配的，对于'a'也是一样，原因就在于T[1] = T[3]。

或者说：T[3] = T[next[3]]，即T[j] = T[ next[j] ]。

出现这种情况时，让j = next[j]的下一步仍然是不匹配的，因此我们可以对get_next函数进行改进：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void get_next(string T, int next[])
{
unsigned int j=0;
int k=-1;
next[0] = -1;
while(j < T.length()-1)
{
if(k==-1 || T[j]==T[k])
{
//修改这里
if(T[++j] == T[++k])
//这种情况一定不匹配
next[j] = next[k];
//故把k=next[k]; next[j]=k; 这两步合到一起
else
next[j] = k;
}
else
k = next[k];
}
}

可以看到，其实就是在if判断里又加了一个判断，当T[++j] == T[++k]时，下一步还是会出现不匹配的情况，因此把next[j]=k; k=next[k];这两步合到一起，就有了next[j] = next[k].

最后

以上就是有魅力指甲油最近收集整理的关于我所理解的KMP算法以及改进的全部内容，更多相关我所理解内容请搜索靠谱客的其他文章。