字符串笔记

本文介绍在OI中常用的字符串算法及个人的一些刷题心得

Rabin-Karp

Rabin-Karp是一种$O(n)$预处理、$O(1)$得到字符串及其子串的Hash值的算法。

代码

本人比较喜欢双取模Hash,一个自然溢出,一个对19260817取模。

  • $kBase$应大于字符集大小
  • 注意Hash值正负的问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Hash {
public:
Hash(char *ch) {
int len = strlen(ch+1);
hash1_[0] = hash2_[0] = 0;
for (int i = 1; i <= len; ++i) {
hash1_[i] = hash1_[i-1]*kBase + ch[i] - 'a';
hash2_[i] = (hash2_[i-1]*kBase + ch[i] - 'a') % kP;
}
}
static void init() {
mi1_[0] = mi2_[0] = 1;
for (int i = 1; i < kLen; ++i) {
mi1_[i] = mi1_[i-1] * kBase;
mi2_[i] = mi2_[i-1] * kBase % kP;
}
}
std::pair<ll, ll> GetHash(int l, int r) {
std::pair<ll, ll> ans;
ans.first = hash1_[r] - hash1_[l-1]*mi1_[r-l+1];
ans.second = ((hash2_[r]-hash2_[l-1]*mi2_[r-l+1])%kP+kP)%kP;
return ans;
}
private:
static const ll kBase = 27, kP = 19260817;
static ll mi1_[kLen], mi2_[kLen];
ll hash1_[kLen], hash2_[kLen];
};
ll Hash::mi1_[kLen], Hash::mi2_[kLen];

拓展应用

暂时还不知道有什么其他的应用,欢迎在评论区补充。


KMP

1
2

版权声明: 本博客所有文章除特别声明外,均采用CC BY-NC-SA 4.0 许可协议。转载请注明出处!

~感谢投食~