字符串处理相关模板


在这里放一些自己打过的板子,备忘好了。
辣鸡博主不会后缀数组 $\mathrm{or}$ 后缀自动稽,好不容易学会的 $\mathrm{AC}$ 自动稽也忘掉了……

哈希

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const int base = 73, mod = 1000003;
int val[10000 + 5];

inline int calc(char ch) {
if(isdigit(ch)) return ch - '0' + 1;
else if(islower(ch)) return ch - 'a' + 11;
else if(isupper(ch)) return ch - 'A' + 37;
}
// 计算某一个字符串的前缀希值
len = strlen(ch);
val[0] = calc(ch[0]);
for (int i = 1; i < len; ++i) {
val[i] = val[i - 1]*base + calc(ch[i]);
if (val[i] >= mod) val[i] -= mod;
}
// 通过前缀哈希值求子段哈希值
ans = (val[r] - val[l - 1]*pow(base, r-l+1)%mod + mod) % mod;

KMP 算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// s1 是文本串,s2 是模板串
p = 0;
for (int i = 2; i <= l2; ++i) {
while (p && s2[p+1]!=s2[i])
p = fail[p];
if (s2[p+1] == s2[i]) p++;
fail[i] = p;
}
p = 0;
for (int i = 1; i <= l1; ++i) {
while (p && s2[p+1] != s1[i])
p = fail[p];
if (s2[p+1] == s1[i]) p++;
if (p == l2) submit(i - l2 + 1); // 匹配成功一次
}

Manacher 算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int nowm = 1, nowr = 1, len = 1, ans = 0;
s[len] = '~', res[len] = 1;
while (isalpha(ch = getchar()))
s[++len] = ch, s[++len] = '~';
for (int i = 2; i <= len; ++i) {
if (i <= nowr)
res[i] = min(res[(nowm<<1)-i], ((nowr-i)<<1)+1);
else res[i] = 1;
int l = (res[i]>>1)+1;
while (i+l <= len && i-l && s[i+l] == s[i-l])
l++, res[i] += 2;
if (nowr < i+l-1)
nowr = i+l-1,
nowm = i;
}
for (int i = 1; i <= len; ++i)
ans = max(ans, res[i]);

$\mathrm{AC}$ 自动机

没有封装,没有指针,用的是char[]而不是std::string
这很不$\text{Sparky_14145}$。
我可怜的代码背叛了我!

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
int newNode() {
fail[++ptr] = 0, end[ptr] = 0;
for (int i = 0; i < 26; ++i)
next[ptr][i] = 0;
return ptr;
}

void init() {
ptr = 0;
root = newNode();
fail[root] = root;
}

void insert(const char *s, int p) {
// 插入一个模板串 s
int cur = root, len = strlen(s);
for (int i = 0; i < len; ++i) {
if (!next[cur][s[i] - 'a'])
next[cur][s[i] - 'a'] = newNode();
cur = next[cur][s[i] - 'a'];
}
end[cur] = p;
}

void build() {
std::queue<int> q;
for (int i = 0; i < 26; ++i) {
if (next[root][i])
fail[next[root][i]] = root,
q.push(next[root][i]);
else
next[root][i] = root;
}
while (!q.empty()) {
int p = q.front();
q.pop();
for (int i = 0; i < 26; ++i) {
if (next[p][i])
fail[next[p][i]] = next[fail[p]][i],
q.push(next[p][i]);
else
next[p][i] = next[fail[p]][i];
}
}
}

int query(const char *s) {
int cur = root, len = strlen(s), ans = 0;
for (int i = 0; i < len; ++i) {
cur = next[cur][s[i] - 'a'];
int temp = cur;
while (temp != root) {
if (end[temp])
ans = std::max(ans, ++cnt[end[temp]]);
temp = fail[temp];
}
}
return ans;
}

后缀数组,$\mathrm{SA}$

构造

感觉基数排序好难啊QwQ。

currprev 是两个 int *

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
30
31
32
33
34
35
for (int i = 0; i < n; ++i)
m = std::max(m, s[i] - 47),
++cnt[prev[i] = s[i] - 48];
for (int i = 1; i < m; ++i) cnt[i] += cnt[i - 1];
for (int i = n - 1; i >= 0; --i) sa[--cnt[prev[i]]] = i;
for (int l = 1; l <= n; l <<= 1) {
int tot = 0;
// 长度不足 l + 1 的后缀
// 这一部分由于第二关键字都是0,故可以以任意顺序排序
for (int i = n - l; i < n; ++i) curr[tot++] = i;
// 此时 curr[i] 表示按次要关键字排序之后排名为 i 的后缀的编号
for (int i = 0; i < n; ++i) if (sa[i] >= l) curr[tot++] = sa[i] - l;

// 清零前缀和数组
for (int i = 0; i < m; ++i) cnt[i] = 0;
// prev 后面的方括号里面只要保证填充完 [0, n) 即可,顺序无所谓
// prev[i] 表示前缀 i 按照第一关键字排序后的排名
for (int i = 0; i < n; ++i) ++cnt[prev[i]]; // 基数排序:统计元素数量
// 基数排序:前缀和快速求排名
for (int i = 1; i < m; ++i) cnt[i] += cnt[i - 1];
// 这层循环顺序不能变
// 将排序结果写入 sa 数组
for (int i = n - 1; i >= 0; --i) sa[--cnt[prev[curr[i]]]] = curr[i];

// 原来的 curr 失效
std::swap(prev, curr);
tot = 1, prev[sa[0]] = 0;
// 计算下一轮的 prev 数组
for (int i = 1; i < n; ++i)
prev[sa[i]] = curr[sa[i-1]]==curr[sa[i]]
&& curr[sa[i-1]+l]==curr[sa[i]+l]
? tot - 1 : tot++;
if (tot >= n) break; // 如果已经有了 n 个不同的排名
m = tot; // 下一轮排序不同的第二关键字数量
}

 评论