字符串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做函数名！）

1

2

3

4

5

6

7

int ahash(string s) {

int h = 0;

for (int i = 0; i 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的代码）

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

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

#include

#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 

string s;

cin >> s;

node *r = root;

for (int j = 0; j 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 

string s;

cin >> s;

node *r = root;

bool flag = false;

for (int j = 0; j size(); j++) {

int ii = id(s[j]);

if (r->z[ii] == nullptr) {

flag = true;

break;

}

r = r->z[ii];

}

if (!flag) cout count 

else cout 0 

}

// 查询

}

int main() {

ios::sync_with_stdio(false);

cin.tie(nullptr);

int n;

cin >> n;

while (n--) {

s();

}

return 0;

}

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