提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

字符串问题 笔记

笔记
2023-02-26 09:50:10 时间

字符串Hash，KMP，字典树的一些笔记

字符串Hash

这是什么

一个可以将任意长度的字符串映射为一个非负整数的算法。即，不同的字符串映射出不同的值，相同的映射出相同的值。

原理

将字符串视作一个 P 进制的数，对于字符串中的每个字符分配一个数值

字符集是字符串中有可能出现的字符的一个集合，如，小写字母的字符集为 {a, b, c, d, …, z}

同样以小写字母为例，分配 a=1, b=2, …

一般情况下，将 P 设为 13331 即可

但如果串很长（10^5） 就会超出 int 类型的范围。碰到这种情况，可以使用 unsigned long long int 存储Hash值，它会自动对数值进行取模，比手动取模快不少

但这样一来，就可能出现Hash冲突，请设想这样一种情况：A字符串的Hash为 h ，B字符串的Hash为 h + 模数，那么它们取模后的Hash值是一样的，怎么办呢？

可以多模：用多个模数同时模字符串的Hash，但模数的数量不要超过2个，否则容易TLE！

几个对字符串的操作对Hash值的影响：

插入单个字符

对字符串 S 插入一个字符 C ：（ H 指字符串的Hash值， V 指给字符分配的数值，下同）

H(S+C)=H(S)*P+V(C)

两个字符串相减

已知字符串 S+T 、 S 的Hash值， T 的Hash值：（ K 为 T 的长度）

H(T)=H(S+T)-H(S)*P ^ K

（预处理 P 的若干次方！）

前缀和

由前面可知，字符串的Hash值具有可加和可减性，由此可以使用前缀和来处理字符串Hash值。

时间复杂度：以 O(K) 的时间复杂度来处理 S 的每个前缀Hash值；以 O(1) 的时间复杂度查询任意长度字串的Hash值

代码

获取字符串Hash值的函数：（不要用hash做函数名！）

int ahash(string s) {
	int h = 0;
	for (int i = 0; i < s.size(); i++) {
		h = h * 27 + (s[i] - 'a' + 1);
	}
	return h;
}

KMP

待补充

字典树

这是什么

一类 K 叉树，用于字符串的快速检索

原理

当要插入一个字符串 S 时，先将 R 置为 K 叉树的根节点上，对 S 中的每一个字符执行以下操作：

如果 R 上的 S_i 为空，则在 R 的 S_i 边新建一个节点并将 R 置于新建的节点上；否则将 R 移动过去

结束后，在 R 上写入一个结束标志，完成！

代码

（这是P8306的代码）

你别问我为什么要用指针做！

#include<iostream>
#define el endl
#define ll long long
using namespace std;
struct node {
	node *z[63] = {nullptr};
	int count = 0;
};
int id(char s) {
	if (s <= 'Z' && s >= 'A') return s - 'A' + 1;
	if (s <= 'z' && s >= 'a') return s - 'a' + 1 + 26;
	return s - '0' + 52 + 1;
}
// 获取单个字符的编号
void s() {
	node *root = new node;
	int a, b;
	cin >> a >> b;
	for (int i = 0; i < a; i++) {
		string s;
		cin >> s;
		node *r = root;
		for (int j = 0; j < s.size(); j++) {
			int ii = id(s[j]);
			if (r->z[ii] == nullptr) r->z[ii] = new node;
			r = r->z[ii];
			r->count++;
		}
	}
	// 输入
	for (int pp = 0; pp < b; pp++) {
		string s;
		cin >> s;
		node *r = root;
		bool flag = false;
		for (int j = 0; j < s.size(); j++) {
			int ii = id(s[j]);
			if (r->z[ii] == nullptr) {
				flag = true;
				break;
			}
			r = r->z[ii];
		}
		if (!flag) cout << r->count << el;
		else cout << 0 << el;
	}
	// 查询
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin >> n;
	while (n--) {
		s();
	}
	return 0;
}

话说这题调了好久，发现是第24行的 j 写成了 i …

相关文章