KMP算法

KMP算法中最核心的一个思想就是回溯。理解该算法的难点就在于回溯到哪个位置, 为什么要回溯到这个位置。

首先, 来看一个例子, 这个例子中两串字符串, 上面的称为串A简称A, 下面的称串B简称B, 编程的目标是要从A中匹配B, 并返回A中匹配到的B位于A中的索引。

可以看到A和B的前6个字母完全相同, 第7个字符不相同

按照普通的匹配算法, 下面应该继续按照如下图所示:




来分析一下上面4个步骤，其是否有必要性。

看下面这张图, 串B索引0与索引从1-3的字符完全不相等。也就是说前4个字符是完全不同的4个字母, 且串B的前4个字符与串A一一对应且相等。由于串B前4字符各不相同且与串A一一对应, 那上图步骤1-3中就没任何意义。就相当于串B索引0分别和自己的索引1-3进行对比, 显然都不可能相等的。可以直接省略

按照上图所示, 前面4个字符不需要比较, 直接从A串的索引4即第5个字符开始匹配。

串B和串A的匹配为何从串B的索引0与串A的索引4开始呢? 下图中可以发现串B中索引0, 1与索引4, 5是对称的。而串B的索引4, 5与串A的索引4, 5又是相等的。

但是串A的索引6与串B的索引2还没有进行对比，这是有可能相同的。看看下图红框中的两次匹配。这两次匹配是否有必要呢?这是没必要的, 因为B串中的索引0, 1和索引4, 5相同。而B串的索引4, 5又和A串的索引4, 5相同。这就可以推出B串的索引0, 1与A串的索引4, 5相同。所以可以直接从B串的索引2与A串的索引6开始匹配。

上面就是为什么回溯, 回溯到哪里的分析。所以可以知道B内必须要有对称的字符才行。通过这种规律, 可以找到一个对应于模式串的回溯数组, 称作next数组, 该数组内装着的都是B串该回溯到哪个位置, A串永远不会回溯只会往前走。

实际上该回溯的本质就是由于有对称内容且之前的字符各不相等, 只要从对称的地方后面开始匹配即可。为了寻找这个next数组，我们需要找到其中对称的内容, 来看一下对称的极端情况:如果蓝线和绿线所覆盖的内容相同, 则这就是最极端的对称情况。

为了寻找对称情况, 我们可以这样来扫描, 首先可以知道索引0是无法回溯的, 因为它是第一个, 所以索引0回溯到的地方还是索引0, 在next数组中就体现在next[0] = 0

来看一下寻找next数组的cpp代码。
解释一下:

1. 如果str[i]和str[j]相等代表至少有1个字符对称, 并且会继续匹配下去
2. 看如下图, 由于ab两个字母是对称的而c和d不同, 如果该串和另一个串进行匹配, 假设那个串叫C, 索引0~5都相同, 但索引6不同时, 这就意味着可以让C直接和这个串的索引2开始比较。也就是说next[5] = 2, 一旦该串的索引6匹配失败, 可以直接回溯到next[6 - 1]即next[5]也就是2。
   

vector<int> getNext(string str)
{
	int j = 0, i = 1;
	vector<int> vecNext(str.size(), 0);

	for (i = 1; i < str.size(); ++i)
	{
		while (j > 0 && str[i] != str[j])
		{
			j = vecNext[j - 1];
		}
		if (str[i] == str[j])
		{
			++j;
		}
		vecNext[i] = j;
	}  

	return(vecNext);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

有了next数组, KMP算法就很简单了, 只是把回溯值变成next数组内的值:

  int KMP(string s, string t)
    {
    	int i = 0, j = 0;
    	vector<int> next;
    
    	next = getNext(t);
    
    	while (t[j] && s[i])
    	{
    		if (s[i] == t[j])
    		{
    			++i;
    			++j;
    		}
    		else
    		{
    			if (j > 0)
    			{
    				j = next[j - 1];
    			}
    			else
    			{
    				++i;
    			}
    		}
    	}
    	if (!s[i] && t[j])
    	{
    		return(-1);
    	}
    	return(i - j);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32