字符串哈希
相关定义与基本性质
字符串哈希的定义 字符串哈希指将一个字符串单向映射到一个整数的方法。
约定 \(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\) ,有如下公式:
关于冲突率 若我们将模运算结果视作均匀分布在 \([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]\) 的哈希值,我们只需要计算下式即可:
关于常数 在 \(\sum|S_i| = 10^7\) 左右,单哈(无/O2)430ms/70ms,双哈(无/O2)800ms/300ms。
注意使用前先 init_pB
预处理 pB
数组。
时间复杂度:
- 预处理 \(O(|S|)\)
- 子串查询 \(O(1)\)
空间复杂度 \(O(|S|)\)
template 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 vector<vector<int>> StrHash::pB;
线段树维护带修多项式取模哈希
参考例题 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 node; vector 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 &src) { init(src); } void init(int _n) { n = _n; node.assign(n << 2, T()); lazy.assign(n << 2, F()); } void init(const vector &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 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> 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()); vector 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 vector<vector<int>> StrHash::pB; template vector<vector<int>> StrHash::pBsum;
字符串哈希的相关应用
字符串匹配
在匹配串 \(S\) 中找匹配模式串 \(P\) 的子串的左端点 \(pos\) 。
直接判断对应串的哈希值是否相等即可。
时间复杂度 \(O(|S| + |P|)\)
空间复杂度 \(O(|S| + |P|)\)
template vector<int> match(const T &s, const T &p) { int n = s.size() - 1, m = p.size() - 1; StrHash 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 vector<int> LCP_k(const T &s, const T &p, int k) { int n = s.size() - 1, m = p.size() - 1; StrHash 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 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 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 s_hash(T(s.begin(), s.end() - 1)); StrHash 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
存储哈希值,而默认哈希函数没有支持这个容器的哈希函数。
当然也可以不使用 unordered
系列,但复杂度会多个 \(\log\) (本身常数就很大了qwq)。
时间复杂度 \(O(\sum|S_i| \cdot\log\min \{ |S_i|\})\)
空间复杂度 \(O(\sum|S_i|)\)
template 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 int LCS(const vector &s) { int n = s.size() - 1; int len = 1e9; vector> 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; }