字符串笔记

Link_Cut_Y · 2023-06-20 18:26:51 · 算法·理论

今天重新拾起字符串。其实本来早就学过的，但是早就忘光了。所以复习一下，笔记记在这里，以免自己以后再忘掉。

字符串哈希

什么是字符串哈希

将某个字符串压缩成一个数字的方法。

设字符串为 S。其对应的唯一的哈希值为 \mathrm{hash_{S}} = \sum \limits_{i = 1}^{|S|} S_i b ^ {|S| - i} \bmod P。也就是对应了一个 b 进制的数。

对于哈希有两条性质：

1. 哈希值不同的两个字符串一定不相等。

2. 哈希值相同的两个字符串不一定相等。这也就是所谓的哈希冲突。

哈希冲突的概率与 P 的大小成反比。因此需要选择大质数来做模数，以避免哈希冲突。

如何求字符串哈希

按照定义模拟即可。时间复杂度 \Theta(|S|)。

如何求子串哈希

假设要求子串 S[l \sim r] 的哈希值。设 S[1 \sim r] 的哈希值为 \mathrm{hash_r}，S[1, l - 1] 的哈希值为 \mathrm{hash_{l - 1}}。那么可以看出，\mathrm{hash_{r}} = \sum \limits_{i = 1}^{r} S_i b ^ {r - i}， \mathrm{hash_{l - 1}} = \sum \limits_{i = 1}^{l - 1} S_i b ^ {l - i - 1}。因此求子串哈希 \mathrm{hash_{S[l, r]}} = \mathrm{hash_r} - \mathrm{hash_{l - 1}} \times b ^{r - l + 1}。

其他技巧

1. 由于取模需要很长时间，在实现过程中可以用 unsigned int 或 unsigned long long 来存储哈希值。由于 unsigned 有自动溢出的特性，这样相当于自动对 2 ^ {31} - 1 / 2 ^{64} - 1 取模了。

2. 如果担心有人卡哈希，可以尝试一下换个模数或者写双哈希。

哈希模板：

struct hash_string {
    string S; int mod, p;
    vector<long long> h;
    vector<long long> p_pow;
    hash_string() {}
    hash_string(int mod, int p):mod(mod), p(p) { p_pow.emplace_back(1ll); h.emplace_back(0ll); }
    hash_string(string S, int mod, int p) : S(S), mod(mod), p(p) { // 初始化字符串和模数
        p_pow.emplace_back(1ll); h.emplace_back(0ll);
        for (auto c : S) {
            h.emplace_back((h.back() * p + c) % mod);
            p_pow.emplace_back(p_pow.back() * p % mod);
        }
    }
    void insert(char c) { // 插入字符
        S += c; h.emplace_back((h.back() * p + c) % mod);
        p_pow.emplace_back(p_pow.back() * p % mod);
    }
    int hash_value(int l, int r) { // 查询哈希值
        return ((h[r] - h[l - 1] * p_pow[r - l + 1] % mod) % mod + mod) % mod;
    }
};

struct double_hash {
    string S; hash_string hash1, hash2;
    double_hash() {}
    double_hash(string S) : S(S) { // 初始化。传入字符串，哈希模数为原定。
        hash1 = hash_string(S, (int)1e9 + 7, 1331);
        hash2 = hash_string(S, (int)1e9 + 9, 1331);
    }
    double_hash(string S, int mod1, int p1, int mod2, int p2) : S(S) { // 初始化，传入字符串和哈希模数
        hash1 = hash_string(S, mod1, p1);
        hash2 = hash_string(S, mod2, p2);
    }
    bool equal(int l1, int r1, int l2, int r2) { // 判断两段串是否相等。
        return (hash1.hash_value(l1, r1) == hash1.hash_value(l2, r2) and
                hash2.hash_value(l1, r1) == hash2.hash_value(l2, r2));
    }
    void insert(char c) { // 插入字符
        hash1.insert(c), hash2.insert(c);
    }
};

例题

\text{P3805 【模板】manacher 算法}

线性时间内求出最长回文子串。

显然，这道题需要用 \text{manacher} 算法来做。但是哈希也可以线性水过。

先求一遍正反哈希，然后枚举回文中心。再枚举回文长度 k。这里的 k 是指回文中心前后相同的长度都为 k。然后在用哈希判断是否相等。

这样只能解决奇串？分讨或者在中间加空白字符就好了嘛。

现在在模板串的第 6 的字符失配了。应该是 \texttt{c}，但是匹配到了 \texttt{a}。

如果按照原来的暴力，就需要这样移动：

但是这样第一个字符明显是无法匹配的，这样白白浪费了时间。

因此考虑像这样移动：

我拿彩色框框框起来的都是相同的子串。可以看出，这样前三个字符是一定匹配的。这样就很优秀。

也就是说，我们要首先找到 失配字符之前的子串最长相同前后缀，然后把模式串的前缀移动到和后缀匹配起来。

也就是说像下面的情景：

现在红色的串都相等，蓝色的字符和绿色的字符是第一个失配的字符。那么需要这样移动：

可以看出，现在第一个串的第二个红色段和第二个串的第一个红色段还是匹配的，这样就省了许多移动。现在就只需要比较绿色和紫色字符是否一样就行了。如果不一样，继续按照上面的说法，求出红色串的 \text{border}，然后重复操作就可以了。

如何证明复杂度是 O(n) 的？不会。大概是因为短串单调右移？

char s[N], p[N];
int n, m, ne[N];

int main() {
    scanf("%s", s + 1); // s 为模式串
    scanf("%s", p + 1); // p 为模板串
    n = strlen(s + 1), m = strlen(p + 1);
    for (int i = 2, j = 0; i <= m; i ++ ) {
        while (j and p[i] != p[j + 1]) j = ne[j];
        if (p[i] == p[j + 1]) j ++ ;
        ne[i] = j; // ne 存的是每个前缀串的 border
    }

    for (int i = 1, j = 0; i <= n; i ++ ) {
        while (j and s[i] != p[j + 1]) j = ne[j];
        if (s[i] == p[j + 1]) j ++ ;
        if (j == m) {
            printf("%d\n", i - m + 1);
            j = ne[j];
        }
    }

    for (int i = 1; i <= m; i ++ )
        printf("%d ", ne[i]);
}

字典树 trie

允许使用单次 O(|T|) 复杂度匹配多字符串的算法。

从根节点开始，每个节点指出大小为字符集的出边。没什么好说的，一万年以后我也会。

建议用指针建，省空间。

\text{P2580 于是他错误的点名开始了}

struct node {
    bool end, repeaten;
    node *s[26];
    node() {
        end = false, repeaten = false;
        for (int i = 0; i < 26; i ++ )
            s[i] = nullptr;
    }
}*root;

void insert(node *u, string str) {
    if (str.empty()) { u -> end = true; return; }
    int c = str[0] - 'a'; str.erase(str.begin());
    if (u -> s[c] == nullptr) u -> s[c] = new node();
    insert(u -> s[c], str);
}
string query(node *u, string str) {
    if (str.empty()) {
        if (!u -> end) return "WRONG\n";
        if (u -> repeaten) return "REPEAT\n";
        u -> repeaten = true; return "OK\n";
    }
    int c = str[0] - 'a'; str.erase(str.begin());
    if (u -> s[c] == nullptr) return "WRONG\n";
    return query(u -> s[c], str);
}

01 trie

不想写了，反正会写。也就求个最大 \operatorname{xor} 和。

思路大概就是根据异或的性质进行贪心。

AC 自动机