萌新菜鸡算法笔记No.1 KMP算法 2017/8/25

最近做了几道kmp算法的题，感觉还不是很熟练，特此总结一番。

kmp算法是用来进行字符串串匹配的算法，就是一个主串a，和一个串b，可以算b在a中出现了几次。

这里的子串是指，假设b长度为lb，从串a的某个位置开始lb个字符都和b相同（等于是b嵌在了a中），则称b是a的字串，b在a出现过。

好了，我们先回顾一下朴素的字符串匹配。我们现在有主串a和一个串b。我们先找到a的一个位置j使b[0]==a[j]，然后在检查b[k]==a[j+k]，其中k=1 to lb。如果发现不相同了，我们仅仅是将b串往后挪一位，看下一个a[j]是否等于b[0]。这样的话算法包含一个双重循环，时间复杂度是O(la*lb)。

但实际上我们可以发现这样找有点浪费时间，比如说a = "tomatomatos"中找b = "tomatos"这个串，从a[0]开始比较找到a[6]='m' 和b[6]='s' 不同时，我们人脑搜应该从a[4]从新开始比较第三位，而不是a[1]。因为b[4-5]和b[0-1]是一样的，这个时候我们可以将b串往后挪4位，而不是1位。换句话说，b[0-5]="tomato"这个串，prefix(2)和suffix(2)是相同的。（prefix(x)指前x个字符，而suffix指后缀）

然后就可以开始搞了。我们假设搜到j+1位不同了，前j位是相同的。 就拿刚刚的tomatomatos和tomatos来说吧，假如我们能知道b[5]==a[5]而b[6]!=a[6]，然后我们又知道b[0-5]中有suffix(2)==pre(2)==k，然后我们就可以将b串往后挪6-k个位置了。这里的6正好是已经匹配成功的那个“6”个字符，而k是最大的suffix(k)==prefix(k)。

也就是说，加入我们有这个关于前缀和后缀最大相等数的信息，就可以每个字符指比较一次地算完整个串匹配的过程了，时间复杂度位O(la)。然后我们还可以惊奇的发现，这个信息可以在O(lb)时间之内完成。

接下来请不要吐槽我的渣渣画图水平

我们发现有一个很明显的递推关系：若pre[j]表示b[0-j]中，最大的suffix(k)==prefix(k)，那么当b[j]==b[pre[j-1]+1]时，pre[j]=pre[j-1]+1;当b[j]!=b[pre[j-1]+1]时，pre[j]=0，因为前后缀关系全乱了，要从新开始算了。这部分可能有些无法理解，如果有困惑的话请自己多来几个例子验证一下。

然后有了pre数组，就知道每次遇到字符a[now+j]!=b[j]时，应该把b往后挪几位（相当于改变now的值）

这里给一份hdu2087的一份超丑代码，不知道能不能提供点帮助

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
using namespace std;
string a, b;
const int maxn = 1000 + 10;
int pre[maxn];
int la, lb;
void kmp() {
	int ans = 0;
	//memset(pre, 0, sizeof(pre));
	pre[0] = 0;
	for (int i = 1; i < lb; ++i) {
		if (b[i] == b[pre[i - 1]]) pre[i] = pre[i - 1] + 1;
		else pre[i] = 0;
	}
	//arr:pre
	int now = 0, j = 0;
	while (now + j < la) {
		if (a[now + j] == b[j]) {
			j++;
			if (j == lb) {
				++ans; now = now + j; j = 0;
			}
			if (now + j >= la) break;
		}
		else {
			if (pre[j - 1] == 0) ++now;
			else now += j - pre[j - 1];
			j = pre[j - 1];
		}
		if (now + j >= la) break;

	}
	cout << ans << endl;
	return;
}
int main()
{
	cin >> a;
	while (a != "#") {
		cin >> b;
		la = a.length(); lb = b.length();
		kmp();
		cin >> a;
	}

    return 0;
}