字符串哈希 模板

本文参考自：

• 字符串Hash总结 | 远航休息栈

---

模板

namespace StringHash {
    const int MAXN = 1e5 + 50;
    const unsigned long long BASE = 131;
    char s[MAXN]; // cin >> (s + 1);
    int len;
    unsigned long long hash[MAXN], power[MAXN];

    inline void preHash() {
        power[0] = 1;
        for (int i = 1; i <= len; i++) 
            power[i] = power[i - 1] * BASE;
    }

    inline void calcHash() {
        for (int i = 1; i <= len; i++) {
            hash[i] = hash[i - 1] * BASE + s[i];
        }
    }

    inline unsigned long long getHash(int l, int r) {
        return (unsigned long long)hash[r] - hash[l - 1] * power[r - l + 1];
    }

    inline void input() {
        cin >> (s + 1);
        len = strlen(s + 1);
    }
}

int main() {
    StringHash::input();
    StringHash::preHash();
    StringHash::calcHash();
    cout << StringHash::getHash(1, 2) << endl;

    return 0;
}

---

字符串哈希实现其他算法

KMP

给两个字符串 S1、S2，求 S2 是否是 S1 的字串，并求出 S2 在 S1 中出现的次数。

将 S2 哈希后，在 S1 中查询所有长度为 $|S2|$ 的字串，并进行哈希比较。

复杂度：$O(|S1|)$。

AC 自动机

给出 N 个单词串，和一个文章串，求每个单词串是否是文章串的子串，并求每个单词在文章中出现的次数。

先把每一个单词串哈希，再把文章的每一个子串也进行整数，接下来只需要进行整数上的查找即可。

复杂度：$O(|A|^2+|S|)$。$|S|$ 是单词串总长，$|A|$ 是文章串长度。

后缀数组

给出两个字符串 S1、S2，求它们的最长公共子串的长度。

将 S1 的每一个子串都哈希成一个整数，再对 S2 的每一个字串进行哈希，并判断是否与 S1 的某一个字串相同，不断维护相同的字串的长度最大值即可。

复杂度：$O(|S1|^2+|S2|^2)$。

马拉车

给一个字符串 S，求 S 的最长回文子串。

将 S 从前后两个方向分别进行字符串哈希。
对子串长度为奇数和偶数的情况分别进行求解。
枚举回文子串的中心位置，然后二分子串的长度，直到找到一个该位置的最长回文子串，不断维护长度最大值即可。

复杂度：$O(|S|log|S|)$。

扩展 KMP

给一个字符串 S，求 S 的每个后缀与S的最长公共前缀。

枚举每一个后缀的起始位置，二分长度，求出每个后缀与S的最长公共前缀。

复杂度：$O(|S|log|S|)$。