关于kmp算法的next数组化简的讲解,以及kmp的替代品“哈希表”

关于kmp算法的next数组化简的讲解,以及kmp的替代品“哈希表”

先说一下kmp吧；

众所周知，kmp的核心是next数组的构造；

这里其实可以化简一下kmp的next数组以便以理解，其核心思想还是一样的，但是那样的话效率会低很多，所以做题的时候千万不要这么写，因为这样只是便于理解；

设字串为abcdabcac；

我们先找到一个“wall”，这个wall是什么意思呢？其意义呢就是最开头的字符第二次出现位置的前一个位置，拿上面那个字符串来理解，就是开头字符为a，其下标为0，然后第二次出现a是下标为4，前面一个位置就是3了，那么我们的wall值就是3；

有了这个wall值我们该怎么办呢？我们要给下标为0~wall的next数组里面填0，然后开始计算wall+1~n的next数组了，到这里就很简单了，先看代码；

#include
#include
using namespace std;
string str;
int ne[100010];
int main() {
	cin >> str;
	int wall = 3;
	for (int i = 0; i <= wall; i++){

		ne[i]=0;//0~wall 全部指向第一个字符

	}
	int n = str.size();
	for (int i = wall + 1; i < n; i++) {//n为字符串长度

		if (str[i] == str[0]) 
            //查看是否有与前缀部分相同的字串，

			for (int j = i, t = 0; t <= wall && str[j] == str[t]; t++, j++) {
				ne[j] = t;//将合格的字串指向开头
				i = j;
			}

		else {

			ne[i] = 0;

		}
	}
	for (int i = 0; i < n; i++)

		cout << ne[i] << ' ';


}

这里的 *** 作其实就是看一下后面的字符串有没有和前面前0~wall相同的字串，有的话就标记next数组为对应的前缀长度，理解这里的话，那么理解kmp就差临门一脚了，因为kmp算法的逻辑有点绕，言语间很难表达，所以就用这种方式简单地理解kmp；

那么重头戏来了，如何用哈希表来替代kmp呢？

我们先来说明一下什么是哈希表，举一个简单的例子，如果让你输入10^6个位于-10^9~10^9的数，然后有m次询问一个数x是否出现过，可能很多人会想到用一个数组来存储每个数出现的次数，但想一下会发现，数组太长了，会爆空间，那怎么办勒？很简单，用一个下标来存多个数出现的次数就行了啊，那该怎么做才能在短空间里来存储那么大的数字呢？用取模，每个数取模的答案是唯一的，所以对应在短空间里的位置也是唯一的，那么我们接下来就是要在一个短空间里来存储多个数字了，这样的话我们就需要用到我们的vector容器了；不晓得这个容器的people可以去问一下度娘，很简单的；

万事先代码

#include
#include
using namespace std;

typedef unsigned long long ull;

const int N = 1000010;

vector< vector > st(N);

int n, m; // 输入个数和询问次数

void insert(ull num) {

	int k = (num % n + n) % n;//取模找到对应位置

	st[k].push_back(num);

}

bool find(int num) {
	int k = (num % n + n) % n;

	for (int i = 0; i < st[k].size(); i++) {//参数应该在的位置循环，看是否有询问的数字存在

		if (st[k][i] == num)

			return true;

	}

	return false;
}

int main() {
	cin >> n >> m;

	for(int i=0;i> num;

		insert(num);

	}

	while (m--) {

		ull num; cin >> num;

		if (find(num)) puts("Yes");

		else puts("No");

	}

}

如果你明白了原理，那么也可以用数组模拟的链表来写，那样的效率可以高一些，但是代码会复杂很多；

哈希表的原理就是映射和处理多对一的冲突；

那么如何用哈希表来替代kmp算法来找字串呢？【说实话，本菜鸟觉得哈希表的逻辑比kmp的要好理解n倍】

给你一个二进制数: 10010100010010;

然后给你一个27进制数： abcdefg;

要知道，二进制数有一个特点，那就是任意的一串二进制数字都有唯一一个10进制数字与之对应，27进制也是一样的，那么我们只需要把我们需要找的字串化为一个10进制数，然后把母串中所有与子串长度一样的串的10径直数算出来，接着一个个与子串比对就行了；

如何算子串的10进制数？

给你一个数：1234567；

你会怎么得到234呢？很简单1234-1000就行了；

27进制数abcdefg中怎么找到bcd的十进制数？很简单，用abcd的10进制数减掉aaaa的就行；

看代码；

#include
#include
#include
using namespace std;

typedef unsigned long long  ull;

const int N = 10000010,base=131;//经验数，当为132进制数时冲突的概率会很小，可以忽略

int cont;//记录子串出现的次数；

ull num[N], p[N];

string a,b;//a为母串，b为子串

ull numa;//子串对应的10进制数


vector< vector> >   st(N);

ull get(int l, int r) {
	return num[r] - num[l - 1] * p[r - l + 1];
}

void insert(ull k, string str, int i) {
	st[k%N].push_back({ str,i });
}

void find(ull numa) {

	int k = numa % N;

	if (st[k].size() == 0)
		cout << "no";
	else {
		for (int i = 0; i < st[k].size(); i++) {
			cout << st[k][i].second <<' ';
		}
	}

}

int main() {
	int len1, len2;
	cin >>len1>> b >> len2>>a;

	

	p[0] = 1;//p[i]里为131^i；
	num[0] = a[0] - 'a' + 1;//0~0的10进制数

	for (int i = 1; i < a.size(); i++) {//计算母串0~i的10进制数

		num[i] = num[i - 1] * base + a[i] - 'a' + 1;
		p[i] = p[i - 1] * base;

	}
	
	numa = b[0] - 'a' + 1;//计算子串的10进制数
	for (int i = 1; i < b.size(); i++) {

		numa = numa * base + b[i] - 'a' + 1;

	}

	for (int i = 0, j = b.size() - 1; j < a.size(); j++, i++) {

		ull mid = get(i, j);//得到母串中所有长度与子串相同的串的10进制数
		
		string str = a.substr(i, b.size());

		insert(mid, str, i);

	}

	find(numa);
	
}

说实话...有点长，也很容易爆内存，但好理解是真的；