字符串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 $...