字符串哈希

快速判断两个字符串是否相等

遇见不定长问题可以通过

单hash

#include <bits/stdc++.h>
using namespace std;
#define ull unsigned long long
const int maxn = 1e5 + 10;
ull hash_[maxn], xp[maxn];

void init()
{
    xp[0] = 1;
    for (int i = 1; i <= maxn; ++i)
        xp[i] = xp[i - 1] * 13331;
    return;
}

void make_hash(string s)
{
    int len = s.length();
    hash_[len] = 0;
    for (int i = len - 1; i >= 0; i--)
    {
        hash_[i] = hash_[i + 1] * 13331 + s[i] - 'A' + 1;
    }
    return;
}

ull get_hash(int l, int len) // 得到起点为l,长度为len的子串的哈希值
{
    return hash_[l] - hash_[l + len] * xp[len];
}

hash的应用

• 字符串匹配

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

  • 给定定长为n的源串s，以及长度为m的模式串p，要求查找源串中有多少字串与模式串匹配；s与p匹配，当且仅当s与p长度相同，且最多有k个位置字符不同
  • 哈希+二分

• 最长公共子字符串

  • 给定 m 个总长不超过 n 的非空字符串，查找所有字符串的最长公共子字符串，如果有多个，任意输出其中一个。
  • 很显然如果存在长度为 k 的最长公共子字符串，那么 k-1 的公共子字符串也必定存在。因此我们可以二分最长公共子字符串的长度。假设现在的长度为 k ，check(k) 的逻辑为我们将所有所有字符串的长度为 k 的子串分别进行哈希，将哈希值放入 n 个哈希表中存储。之后求交集即可。

• 最长回文子串

  • 二分答案

• 确定字符串中不同子字符串的数量