[数据结构与算法]KMP字符串匹配

KMP算法是用来快速进行字符串匹配的，可以找出一个字符串在另一个字符串中出现的位置和次数等有关问题。

基本思想就是先对其中要找的那个子串进行匹配—记录每一个位置当在这个位置匹配的时候出现了问题应该从哪个地方重新开始匹配。

举个栗子吧

如下两个字符串

字符串从下标1开始

s1 = abcabcabcabcd
s2 = abcabcd

当我们要进行暴力匹配的时候，s2字符串匹配到d时，s1为a，此时匹配出现了问题，要重新从上次匹配s1的位置的下一个位置来进行匹配，这时会非常浪费时间，效率太低了。

而我们观察可以发现，匹配的时候前面一段是有相同部分的。s2中有两个abc，而匹配s1的时候前面两个abc是能够匹配成功的。由于是最后的d匹配出现了问题，我们可以直接把匹配的s2的位置移动到第一个abc的后面，这样就可以重新尝试匹配了。

两个abc都是匹配成功的，此时可以将s2的第一个abc转移到第二个的位置

注意此时匹配的s1的下标不发生变化，匹配s2的下标发生变化。

如果转移之后仍然不匹配，就要继续转移，直到转移到s2字符串的起始位置。

next指针

在向前转移的时候对于不同的匹配情况来说转移的长度也有所不同。这时需要对s2进行自我匹配，并用next数组来记录每一个位置下要转移多少。

首先对于第一个字符ne[1] = 0

因为第一个字符匹配失败肯定是要重新匹配的。

所以要第二个字符开始

void get_next()
{
    int j = 0;
    for (int i = 2; i <= lp; i++)
    {
        while(j && p[j + 1] != p[i]) j = ne[j];
        if(p[j + 1] == p[i]) j++; 
        ne[i] = j;
    }
}

下面是一道模板题

P3375 【模板】KMP字符串匹配

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e6 + 10;

char s[N], p[N];
int ls, lp;
int ne[N];

void getNext()
{
	for (int i = 2, j = 0; i <= lp; i++)
	{
		while (j && p[j + 1] != p[i]) j = ne[j];
		if (p[j + 1] == p[i]) j++; 
		ne[i] = j;
	}
}

int main()
{
	cin >> s + 1;
	cin >> p + 1;
	ls = strlen(s + 1);
	lp = strlen(p + 1);
	getNext();
	for (int i = 1, j = 0; i <= ls; i++)
	{
		while (j && p[j + 1] != s[i]) j = ne[j];
		if (p[j + 1] == s[i]) j++;
		if (j == lp)
		{
			cout << i - lp + 1 << endl;
			j = ne[j];
		}
	}
	for (int i = 1; i <= lp; i++)
	{
		cout << ne[i] << ' ';
	}
	return 0;
}

这一篇文章感觉写的多少有点不清楚，因为next指针为什么要那样求自己也不明不白，只知道要那样写，等着以后明白了再更新吧hh~~~