字符串笔记-字符串哈希

转载作者：我是一只小鸟更新时间：2023-09-09 15:01:55

字符串哈希
- 字符串中的哈希
  - 定义与基本性质
  - 多项式取模哈希
  - 代码模板
- 字符串哈希的应用
  - 字符串匹配
  - 允许 $k$ 次失配的最长公共前缀
  - 允许 $k$ 次失配的字符串匹配
  - 允许 $k$ 次失配的最长回文子串
  - 最长公共子串
  - 线段树维护带修字符串哈希

字符串哈希

字符串中的哈希

定义与基本性质

字符串哈希的定义字符串哈希指将一个字符串单向映射到一个整数的方法.

约定 $H(S)$ 表示字符串 $S$ 经由哈希映射 $H$ 得到的一个整数值.

哈希检测的定义通过 $H(S)$ 和 $H(T)$ 是否相等来判断 $S$ 和 $T$ 是否相等的方法，称为哈希检测.

哈希冲突的定义 $H(S) = H(T)$ 但 $S \neq T$ ，即发生哈希冲突.

性质1（必要性） $S = T \Rightarrow H(S) = H(T)$ .

性质2（非充分性） $H(S) = H(T) \not \Rightarrow S = T$ .

多项式取模哈希

将字符串看作某个进制下的一个整数，这个过程为多项式哈希。它本身是零冲突的，但是由于值域过大不易处理，因此对其取模缩小值域，代价是会有较低的冲突率.

形式化地说，对于长度为 $n$ 的字符串 $S$ ，要将其看作 $B$ 进制下的一个整数并模 $P$ ，有如下公式:

\[\begin{aligned} H(S) &= \left( \sum_{i=1}^{n} S[i]\cdot B^{n-i} \right) \bmod P\\ &= \left( S[1] \cdot B^{n-1} + S[2] \cdot B^{n-2} + \cdots + S[n] \cdot B^{0}\right) \bmod P \end{aligned} \]

关于冲突率若我们将模运算结果视作均匀分布在 $[0,P-1]$ 的散列，那么根据生日悖论，在串数超过 $\sqrt P$ 时将有超过 $50 \%$ 的概率发生哈希冲突。因此单模情况下，我们的模数 $P$ 最好超过总串数的平方 .

关于三种取模方式:

自然溢出：用基本类型的范围溢出等价取模，如 ULL 相当于模 $2^{64}$ .

一定被卡。目前已有成熟的方法构造冲突.
单模哈希：选取一个总串数平方级别的质数（一般在 $[10^9,10^{10}]$ ）作为模数.

很大概率被卡。根据生日悖论，串数过大时随机数据都会被卡，但可以选择更大的质数避免.
双模（多模）哈希：选取多个质数作为模数分别单模哈希.

几乎不可能被卡。模数不泄露的情况下，目前没有方法能构造冲突（但你可能中彩票） .

多项式取模哈希求哈希值的过程是可以从左到右递推的，并且通常会保留所有前缀的哈希值 $H(Prefix_S[i])$ ，这是为了利用其具有的前缀和性质，实现 $O(1)$ 的子串哈希值获取，进而实现各种 $O(1)$ 的子串查询.

为了获取子串 $S[l,r]$ 的哈希值，我们只需要计算下式即可:

\[H(S[l,r]) = (H(S[1,r]) - H(S[1,l-1]) \cdot B^{r-l+1}) \bmod P \]

关于常数在 $\sum|S_i| = 10^7$ 左右，单哈(无/O2)430ms/70ms，双哈(无/O2)800ms/300ms.

注意使用前先 init_pB 预处理 pB 数组.

时间复杂度:

预处理 $O(|S|)$
追加 $O(|S|)$
子串查询 $O(1)$

空间复杂度 $O(|S|)$ 。

代码模板

                        
                          template<typename T>
class StrHash {
    const static int HASH_CNT = 2;
    constexpr static array<int, 2> B = { 1212549181, 1580098811 };
    constexpr static array<int, 2> P = { 1795636019, 1706613661 };
    static vector<vector<int>> pB;

    int n;
    vector<vector<int>> hs;

public:
    static void init_pB(int n) {
        pB.assign(HASH_CNT, vector<int>(n + 1));
        for (int id = 0;id < HASH_CNT;id++) {
            pB[id][0] = 1;
            for (int i = 1;i <= n;i++)
                pB[id][i] = 1LL * pB[id][i - 1] * B[id] % P[id];
        }
    }

    StrHash() {}
    StrHash(const T &s) { init(s); }

    void init(const T &s) {
        n = s.size() - 1;
        hs.assign(HASH_CNT, vector<int>(n + 1));
        for (int id = 0;id < HASH_CNT;id++)
            for (int i = 1;i <= n;i++)
                hs[id][i] = (1LL * hs[id][i - 1] * B[id] + s[i]) % P[id];
    }

    vector<int> substr(int l, int r) {
        if (l > r || l < 0) return vector<int>(HASH_CNT);
        vector<int> ans(HASH_CNT);
        for (int id = 0;id < HASH_CNT;id++)
            ans[id] = (hs[id][r] - 1LL * hs[id][l - 1] * pB[id][r - l + 1] % P[id] + P[id]) % P[id];
        return ans;
    }
    vector<int> prefix(int x) { return substr(1, x); }
    vector<int> suffix(int x) { return substr(n - x + 1, n); }
    vector<int> rsubstr(int l, int r) { return substr(n - r + 1, n - l + 1); }
};
template<typename T>
vector<vector<int>> StrHash<T>::pB;

字符串哈希的应用

字符串匹配

在匹配串 $S$ 中找匹配模式串 $P$ 的子串的左端点 $pos$ .

直接判断对应串的哈希值是否相等即可.

时间复杂度 $O(|S| + |P|)$ 。

空间复杂度 $O(|S| + |P|)$ 。

                        
                          template<typename T>
vector<int> match(const T &s, const T &p) {
    int n = s.size() - 1, m = p.size() - 1;
    StrHash<T> s_hash(s), p_hash(p);
    vector<int> pos;
    for (int i = m;i <= n;i++)
        if (s_hash.substr(i - m + 1, i) == p_hash.prefix(m))
            pos.push_back(i - m + 1);
    return pos;
}

允许 $k$ 次失配的最长公共前缀

在匹配串 $S$ 中各个位置开始求与模式串 $P$ 的LCP（允许 $k$ 次失配）.

我们枚举 $S$ 的各个位置作为一开始起点 $cur$ ，注意到LCP具有二分性，因此我们枚举失配之前的LCP的右端点 $pos$ 。此时，若还有失配机会则 $cur = pos+1$ ，否则 $cur = pos$ ，随后继续匹配，直到匹配到不能继续往后或不能继续失配为止.

最后注意 $cur$ 是第一个不能匹配的位置，但这个位置可能是 $n+2$ 或 $i+m+1$ ，所以要处理一下.

时间复杂度 $O(|P| + |S|k\log |S|)$ 。

空间复杂度 $O(|S| + |P|)$ 。

                        
                          template<typename T>
vector<int> LCP_k(const T &s, const T &p, int k) {
    int n = s.size() - 1, m = p.size() - 1;
    StrHash<T> s_hash(s), p_hash(p);
    vector<int> lcp(n + 1);
    for (int i = 1;i <= n;i++) {
        int cur = i;
        for (int j = 0;j <= k && cur <= min(n, i + m - 1);j++) {
            int l = cur, r = min(n, i + m - 1);
            while (l <= r) {
                int mid = l + r >> 1;
                if (s_hash.substr(cur, mid) == p_hash.substr(cur - i + 1, mid - i + 1)) l = mid + 1;
                else r = mid - 1;
            }
            cur = l + (j < k);
        }
        lcp[i] = min({ cur,i + m, n + 1 }) - i;
    }
    return lcp;
}

允许 $k$ 次失配的字符串匹配

在匹配串 $S$ 中找匹配模式串 $P$ 的子串的左端点 $pos$ （允许 $k$ 次失配）.

可以直接利用允许 $k$ 次失配的LCP，若 $LCP = m$ 即匹配成功.

时间复杂度 $O(|P| + |S|k\log |S|)$ 。

空间复杂度 $O(|S| + |P|)$ 。

                        
                          template<typename T>
vector<int> match_k(const T &s, const T &p, int k) {
    int n = s.size() - 1, m = p.size() - 1;
    auto lcp_k = LCP_k(s, p, k);
    vector<int> pos;
    for (int i = 1;i <= n - m + 1;i++) if (lcp_k[i] == m) pos.push_back(i);
    return pos;
}

允许 $k$ 次失配的最长回文子串

对字符串 $S$ 的每个回文对称中心求最长回文半径 $d$ （允许 $k$ 次失配）.

我们将 $S$ 变换成适合枚举回文中心的 $S'$ （与马拉车一致），随后枚举中心二分长度即可，注意二分的边界.

检验通过正序和反序的哈希值，判断相等即可，要注意判断的区间。例如中心是 $i$ ，要判断半径区间 $[cur,mid]$ 子串是否对称，那么需要正序的 $[i-cur+1,i-mid+1]$ 与反序的 $[n-i+1 - cur + 1,n-i+1-mid+1]$ 判断相等.

时间复杂度 $O(|S|k \log |S|)$ 。

空间复杂度 $O(|S|)$ 。

                        
                          template<typename T>
vector<int> LPS_k(const T &_s, int k, T mark = { '$','|','&' }) {
    T s;
    s.push_back(mark[0]);
    s.push_back(mark[1]);
    for (int i = 1;i < _s.size();i++) {
        s.push_back(_s[i]);
        s.push_back(mark[1]);
    }
    s.push_back(mark[2]);

    int n = s.size() - 2;
    StrHash<T> s_hash(T(s.begin(), s.end() - 1));
    StrHash<T> rs_hash(T(s.rbegin(), s.rend() - 1));
    vector<int> d(n + 1);
    for (int i = 1;i <= n;i++) {
        int cur = 1;
        for (int j = 0;j <= k && cur <= min(i, n - i + 1);j++) {
            int l = cur, r = min(i, n - i + 1);
            while (l <= r) {
                int mid = l + r >> 1;
                if (s_hash.substr(i - mid + 1, i - cur + 1) == rs_hash.rsubstr(i + cur - 1, i + mid - 1)) l = mid + 1;
                else r = mid - 1;
            }
            cur = l + (j < k);
        }
        d[i] = min({ i, n - i + 1,cur - 1 });
    }
    return d;
}

最长公共子串

求出字符串组 $S$ 的LCS。不妨设 $|S| = n$ .

显然，LCS具有二分性，因此我们二分长度。对于每一个长度 $x$ ，枚举 $S$ 中各个字符串所有长度为 $x$ 的子串，并根据所属字符串将哈希值存到 unordered_set 中，每个字符串对应的集合表示这个字符串拥有的本质不同的长度为 $x$ 的子串。最后，将所有集合的哈希值放入一个 unordered_map 中，出现 $n$ 次的即为LCS。若存在LCS，那么说明 $x$ 是可行的，否则不可行的.

注意，这里的所有 unordered 需要自定哈希函数，因为使用的双模哈希采用 vector<int> 存储哈希值，而默认哈希函数没有支持这个容器的哈希函数.

当然也可以不使用 unordered 系列，但复杂度会多个 $\log$ （本身常数就很大了qwq）.

时间复杂度 $O(\sum|S_i| \cdot\log\min \{ |S_i|\})$ 。

空间复杂度 $O(\sum|S_i|)$ 。

                        
                          template<typename T>
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }

    size_t operator()(const T &s) const {
        uint64_t res = 0;
        for (auto val : s) res += this->operator()(val);
        return res;
    }
};

template<typename T>
int LCS(const vector<T> &s) {
    int n = s.size() - 1;
    int len = 1e9;
    vector<StrHash<T>> s_hash(n + 1);
    for (int i = 1;i <= n;i++) {
        s_hash[i].init(s[i]);
        len = min(len, (int)s[i].size() - 1);
    }
    auto check = [&](int x) {
        unordered_map<vector<int>, int, custom_hash<vector<int>>> ump;
        for (int i = 1;i <= n;i++) {
            unordered_set<vector<int>, custom_hash<vector<int>>> ust;
            for (int j = x;j <= s[i].size() - 1;j++)
                ust.insert(s_hash[i].substr(j - x + 1, j));
            for (auto hs : ust) ump[hs]++;
        }
        for (auto [hs, cnt] : ump) if (cnt >= n) return true;
        return false;
    };
    int l = 1, r = len;
    while (l <= r) {
        int mid = l + r >> 1;
        if (check(mid)) l = mid + 1;
        else r = mid - 1;
    }
    return r;
}

线段树维护带修字符串哈希

参考例题 CF580E .

为了实现带修，我们需要利用区间维护的利器线段树.

区间合并只需要简单维护一下幂次即可.

区间修改先预处理出 $B$ 等比数列的前缀和 pBsum ，根据需求修改 Func 修改元的信息即可.

单点修改可用不带 lazy 的线段树， pBsum 也可以不用.

注意， Func 中的修改值本身即表示实际值，需要输入之前就 trans 好.

注意使用前先 init_pB 预处理 pB,pBsum 数组.

时间复杂度:

预处理 $O(|S|)$
修改 $O(\log |S|)$
子串查询 $O(\log |S|)$

空间复杂度 $O(|S|)$ 。

                        
                          template<class T, class F>
class SegmentTreeLazy {
    int n;
    vector<T> node;
    vector<F> lazy;

    void push_down(int rt) {
        node[rt << 1] = lazy[rt](node[rt << 1]);
        lazy[rt << 1] = lazy[rt](lazy[rt << 1]);
        node[rt << 1 | 1] = lazy[rt](node[rt << 1 | 1]);
        lazy[rt << 1 | 1] = lazy[rt](lazy[rt << 1 | 1]);
        lazy[rt] = F();
    }

    void update(int rt, int l, int r, int x, int y, F f) {
        if (r < x || y < l) return;
        if (x <= l && r <= y) return node[rt] = f(node[rt]), lazy[rt] = f(lazy[rt]), void();
        push_down(rt);
        int mid = l + r >> 1;
        update(rt << 1, l, mid, x, y, f);
        update(rt << 1 | 1, mid + 1, r, x, y, f);
        node[rt] = node[rt << 1] + node[rt << 1 | 1];
    }

    T query(int rt, int l, int r, int x, int y) {
        if (r < x || y < l) return T();
        if (x <= l && r <= y) return node[rt];
        push_down(rt);
        int mid = l + r >> 1;
        return query(rt << 1, l, mid, x, y) + query(rt << 1 | 1, mid + 1, r, x, y);
    }

public:
    SegmentTreeLazy(int _n = 0) { init(_n); }
    SegmentTreeLazy(const vector<T> &src) { init(src); }

    void init(int _n) {
        n = _n;
        node.assign(n << 2, T());
        lazy.assign(n << 2, F());
    }
    void init(const vector<T> &src) {
        init(src.size() - 1);
        function<void(int, int, int)> build = [&](int rt, int l, int r) {
            if (l == r) return node[rt] = src[l], void();
            int mid = l + r >> 1;
            build(rt << 1, l, mid);
            build(rt << 1 | 1, mid + 1, r);
            node[rt] = node[rt << 1] + node[rt << 1 | 1];
        };
        build(1, 1, n);
    }

    void update(int x, int y, F f) { update(1, 1, n, x, y, f); }

    T query(int x, int y) { return query(1, 1, n, x, y); }
};

template<typename T>
class StrHash {
    const static int HASH_CNT = 2;
    constexpr static array<int, 2> B = { 1212549181, 1580098811 };
    constexpr static array<int, 2> P = { 1795636019, 1706613661 };
    static vector<vector<int>> pB;
    static vector<vector<int>> pBsum;

    struct Node {
        int id = -1;
        int len = 0;
        int hs = 0;
        friend Node operator+(const Node &a, const Node &b) {
            int id = max(a.id, b.id);
            if (id == -1) return Node();
            return{
                id,
                a.len + b.len,
                int((1LL * a.hs * pB[id][b.len] + b.hs) % P[id])
            };
        }
    };

    struct Func {
        int fix = -1;
        Node operator()(const Node &x) {
            if (fix == -1) return x;
            return{
                x.id,
                x.len,
                int(1LL * fix * pBsum[x.id][x.len - 1] % P[x.id])
            };
        }
        Func operator()(const Func &g) {
            if (fix == -1) return g;
            return { fix };
        }
    };

    int n;
    vector<SegmentTreeLazy<Node, Func>> hs;

public:
    static void init_pB(int n) {
        pB.assign(HASH_CNT, vector<int>(n + 1));
        pBsum.assign(HASH_CNT, vector<int>(n + 1));
        for (int id = 0;id < HASH_CNT;id++) {
            pB[id][0] = 1;
            pBsum[id][0] = 1;
            for (int i = 1;i <= n;i++) {
                pB[id][i] = 1LL * pB[id][i - 1] * B[id] % P[id];
                pBsum[id][i] = (0LL + pB[id][i] + pBsum[id][i - 1]) % P[id];
            }
        }
    }

    StrHash() {}
    StrHash(const T &s) { init(s); }

    void init(const T &s) {
        n = s.size() - 1;
        hs.assign(HASH_CNT, SegmentTreeLazy<Node, Func>());
        vector<Node> src(n + 1);
        for (int id = 0;id < HASH_CNT;id++) {
            for (int i = 1;i <= n;i++) src[i] = { id,1,s[i] };
            hs[id].init(src);
        }
    }

    void update(int l, int r, Func f) {
        for (int id = 0;id < HASH_CNT;id++)
            hs[id].update(l, r, f);
    }

    vector<int> substr(int l, int r) {
        if (l > r || l < 0) return vector<int>(HASH_CNT);
        vector<int> ans(HASH_CNT);
        for (int id = 0;id < HASH_CNT;id++)
            ans[id] = hs[id].query(l, r).hs;
        return ans;
    }
    vector<int> prefix(int x) { return substr(1, x); }
    vector<int> suffix(int x) { return substr(n - x + 1, n); }
    vector<int> rsubstr(int l, int r) { return substr(n - r + 1, n - l + 1); }
};
template<typename T>
vector<vector<int>> StrHash<T>::pB;
template<typename T>
vector<vector<int>> StrHash<T>::pBsum;

最后此篇关于字符串笔记-字符串哈希的文章就讲到这里了,如果你想了解更多关于字符串笔记-字符串哈希的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！。

文章推荐： C#结合OpenCVSharp4使用直方图算法比较图片相似度

文章推荐： 2.10PE结构：重建重定位表结构

文章推荐：浅聊一下SpringMVC的核心组件以及通过源码了解其执行流程

文章推荐： IDEFICS简介:最先进视觉语言模型的开源复现

.net - 在sharepoint中使用SPListCollection.Add方法(字符串，字符串，字符串，字符串，Int32，字符串，SPListTemplate.QuickLaunchOptions)
如何使用 SPListCollection.Add(String, String, String, String, Int32, String, SPListTemplate.QuickLaunchO
C++ 字符串 != 字符串
我刚刚开始使用 C++ 并且对 C# 有一些经验，所以我有一些一般的编程经验。然而，似乎我马上就被击落了。我试过在谷歌上寻找，以免浪费任何人的时间，但没有结果。 int main(int argc,
Java 8 : Converting Map>到映射<字符串，字符串[]>
这个问题已经有答案了: In Java 8 how do I transform a Map to another Map using a lambda? (8 个回答) Convert a Map>
node.js - "Type ' 字符串 |字符串[] ' is not assignable to type ' 字符串'
我正在使用 node + typescript 和集成的 swagger 进行 API 调用。我 Swagger 提出以下要求 http://localhost:3033/employees/sear
C++ 映射<字符串， vector <对<字符串，字符串>>> : adding a mapping to an empty vector?
我是 C++ 容器模板的新手。我收集了一些记录。每条记录都有一个唯一的名称，以及一个字段/值对列表。将按名称访问记录。字段/值对的顺序很重要。因此我设计如下: typedef string
java - 谁能帮我创建方法？ mystring.replacefirst(字符串,字符串);并替换(自，直到，字符串)；对于j2me，请
我需要这两种方法，但j2me没有，我找到了一个replaceall();但这是 replaceall(string,string,string); 第二个方法是SringBuffer但在j2me中它没
.net - 字符串 vs 字符串 - 区分大小写的联合
If string is an alias of String in the .net framework为什么会发生这种情况，我应该如何解释它: type JustAString = string
python - 考虑顺序如何检查列表(字符串)是否包含另一个列表(字符串)
我有两个列表(或字符串):一个大，另一个小。我想检查较大的(A)是否包含小的(B)。我的期望如下: 案例 1. B 是 A 的子集 A = [1,2,3] B = [1,2] contains(A
javascript - Jquery 字符串 + 对象 + 字符串
我有一个似乎无法解决的小问题。这里...我有一个像这样创建的输入... var input = $(''); 如果我这样做......一切都很好 $(this).append(input); 如果我
c# - ienumerable <字符串>到列表<字符串>
我有以下代码片段 string[] lines = objects.Split(new string[] { "\r\n", "\n" }, StringSplitOptions.No
Java printf(字符串、Val、字符串)
这可能真的很简单，但我已经坚持了一段时间了。我正在尝试输出一个字符串，然后输出一个带有两位小数的 double ，后跟另一个字符串，这是我的代码。 System.out.printf("成本:%.2
firebase - Cloud Firestore 字符串 >= 字符串
以下是 Cloud Firestore 列表查询中的示例之一 citiesRef.where("state", ">=", "CA").where("state", "= 字符串，我们在Stack O
javascript - if(字符串.包含(字符串))。那可能吗？
我正在尝试检查一个字符串是否包含在另一个字符串中。后面的代码非常简单。我怎样才能在 jquery 中做到这一点？ function deleteRow(locName, locID) { if
C++ 字符串 (int) + 字符串 (int)
这个问题在这里已经有了答案: How to implement big int in C++ (14 个答案) 关闭 9 年前。我有 2 个字符串，都只包含数字。这些数字大于 uint64_t 的
java - 带有自定义转换器的推土机双向映射(字符串，字符串)不可能吗？
我有一个带有自定义转换器的 Dozer 映射: com.xyz.Customer com.xyz.CustomerDAO customerName
java - 字符串 a == 字符串 b 的规则
这个问题在这里已经有了答案: How do I compare strings in Java? (23 个回答) 关闭 6 年前。我想了解字符串池的工作原理以及一个字符串等于另一个字符串的规则是
Swift 字符串 vs. 字符串!与字符串？
我已阅读 this问题和其他一些问题。但它们与我的问题有些无关对于 UILabel 如果你不指定 ? 或 ! 你会得到这样的错误: @IBOutlet property has non-option
c - 字符串 [x] 与 *字符串++
这两种方法中哪一种在理论上更快，为什么？ (指向字符串的指针必须是常量。) destination[count] 和 *destination++ 之间的确切区别是什么？ destination[co
.net - String.Format与“字符串” +“字符串”还是StringBuilder？
This question already has answers here: Closed 11 years ago. Possible Duplicates: Is String.Format a
java - 流<字符串> 到映射<字符串、整数>
我有一个Stream一个文件的，现在我想将相同的单词组合成 Map这很重要，这个词在 Stream 中出现的频率. 我知道我必须使用 collect(Collectors.groupingBy(..)

我是一只小鸟

个人简介

我是一名优秀的程序员,十分优秀！

作者热门文章

滴滴打车优惠券免费领取

全站热门文章

首页

博学

6Ren·AI

商城

字符串笔记-字符串哈希

字符串哈希

字符串中的哈希

定义与基本性质

多项式取模哈希

代码模板

字符串哈希的应用

字符串匹配

允许 \(k\) 次失配的最长公共前缀

允许 \(k\) 次失配的字符串匹配

允许 \(k\) 次失配的最长回文子串

最长公共子串

线段树维护带修字符串哈希