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

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

关于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);
	
}

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

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5718952.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-17
下一篇 2022-12-17

发表评论

登录后才能评论

评论列表(0条)

保存