数据结构-KMP算法

发表于 更新于 分类于

什么是KMP算法

KMP算法要解决的问题就是在字符串（也叫主串）中的模式（pattern）定位问题。说简单点就是我们平时常说的关键字搜索。模式串就是关键字（接下来称它为P），如果它在一个主串（接下来称为T）中出现，就返回它的具体位置，否则返回-1（常用手段）

暴力解法

很容易可以想到暴力解法，直接进行搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
int Findindex(string p,string t){//p是主串，t是模式串
    int i=0,j=0;
    for(i=0;i<p.length();i++){
        if(p[i]==t[j]){
            j++;
        }
        else j=0;
        if(j==t.length()){
            return i-j+1;//因为搜索到之后指针在最后一个对应的位置上
        }
    }
    return -1;
}

显然缺陷在于：回溯过于频繁

KMP算法

1、最长公共前后缀

要理解KMP算法的具体含义，引入最长公共前后缀帮助理解。如下图所示：

显然，字符串$ABCBA$的最长公共前后缀是$ABC$

2、KMP算法的回溯思想

以下方图做例子，观察规律：

可以发现，回溯的位置对应的是最长公共前后缀重合的地方。

下方的理解非常重要，也是$next$数组理解的重要步骤！！！
首先，目标串发生不匹配时的索引—5
然后，回溯的时候目标串的索引与主串的不匹配位置（也就是5）对齐—2。这个2恰好就是目标串发生不匹配位置前的字符串的最长前缀和后缀的长度！

就此引入$next$数组。

$next$数组

再添加几个例子加深理解。

如下目标串的索引为3号的位置发生不匹配：

其3号位置前的字符串的最长相同前后缀的长度是1，所以就应该让目标串索引为1的位置与该不匹配处对齐：

再来，如下目标串的索引为5号的位置发生不匹配：

其5号位置前的字符串的最长相同前后缀的长度是2，所以就应该让目标串索引为2的位置与该不匹配处对齐

$next$数组的求解 （eg: ABCABCMN）
A B C A B C M N
next[0] next[1] next[2] next[3] next[4] next[5] next[6] next[7]
-1 0 0 0 1 2 3 0 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void getnext(string t,int next[])
{
	int j=0,k=-1;
	next[0]=-1;
	while(j<t.size())
	{
		if(k==-1 || str[j]==str[k])
		{
			j++;
			k++;
			next[j]=k;
		}
		else
		{
			k=next[k];
		}
	}
}

3、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[],i=0,j=0;
	getnext(t,next);
	while(i<s.size() && j<t.size())
	{
		if(j==-1 || s[i]==t[j])
		{
			i++;
			j++;
		}
		else
		{
			j=next[j];
		}
	}
	if(j>=t.size())
		return i-t.size();//返回目标串在主串的第一个字符的位置
	else
		return -1;//找不到返回-1

}