问题背景

　　KMP算法是一种优化后的字符串匹配算法，可以将复杂度由暴力匹配的O(m*n)降低到O(m+n)，具体原理就不再赘述，相信几乎任何一本算法书上面都会有KMP算法的详细介绍与实现。以前虽然学习过KMP算法，也清楚算法的原理，但是却从来没有完整实现过一次，闲来无事便打开Visual Studio准备使用C++独立实现一下。

　　代码如下：

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
33
34
35
#include <iostream>
#include <vector>
using namespace std;

//生成模式串对应的next数组
void get_next(const string &p, vector<int> &next) {
	int j = 0;
	int k = -1;
	next[j] = k;
	while (j < p.length() - 1) {
		if (k == -1 || p[k] == p[j]) {
			next[++j] = ++k;
		}
		else {
			k = next[k];
		}
	}

}
//KMP算法实现查找子串
int KMP(const string &str, const string &p) {
	vector<int> next(p.length(), 0);
	get_next(p, next);
	int i = 0, j = 0;
	while (i < str.length() && j < p.length()) {
		if (j == -1 || str[i] == p[j]) {
			i++;
			j++;
		}
		else {
			j = next[j];
		}
	}
	return (j == len_p) ? i - j : -1;
}

我们使用如下代码对上述KMP算法正确性进行验证：

1
2
3
4
5
6
7
8
9
10
int main()
{
	string str = "aabaacg";
	string p = "aac";
	vector<int> next(p.size(), 0);
	get_next(p,next);
	cout << KMP(str, p);
	system("pause");
    return 0;
}

我们可以看到字符串”aac”是包含在”aabaacg”中的，KMP函数应该返回匹配点位置3，但是程序运行后却得到如下结果：

error

KMP函数返回值为-1，即没有在”aabaacg”中找到子串”aac”，显然这个结果并不正确。

问题查找

　　为了找到问题所在，我们单步执行跟踪函数的运行，跟踪结果表明，KMP函数中的循环（代码第25行）在k==-1的情况下退出了，显然这并不符合逻辑。在这个地方仔细想一下就能发现问题出现的原因，我们判断退出条件时使用了vector的成员函数length()获得字符串长度，length()函数返回值为size_t，也就是一个unsigned int类型的值，k的类型却为int，当int与unsigned int比较时，编译器会将int类型转换为unsigned int类型，所以当k==-1时就被转换为了最大的无符号整数INT_MAX，所以k<p.length()条件就不再满足，导致循环提前退出，最终导致函数逻辑出现错误。

　　问题解决办法为在循环前面定义两个int变量len_str和len_p，并将str和p的大小赋值给这两个变量，在循环中使用len_str和len_p替换str.length()和p.length()即可。

总结

这个错误完全是因为编码习惯不够严谨导致的，在C++中随手就会写出这种循环：

1
2
3
for(int i = 0;i < p.length(); i++){
  ...
}

这种代码在 i >= 0 的时候可以运行良好，但是一旦出现i < 0的情况，就会导致意想不到的事情发生。

后面一定要改善自己的编码习惯，对于不同类型之间运算一定要仔细考虑默认类型转换，同时对编译器发出的”waring”引起足够的重视，虽然”waring”不会引起语法错误，但是可能会引起错误代价更大的逻辑错误。