[心之碎片] - 字符串
包括 :哈希, manacher, 字典树, KMP
一些思考:
字符串题首先想哈希
kmp 的求 next 数组过程其实是在 fail 树上的遍历
要善用 next 数组的前后缀相等性质
判断长字符串想倍增比较
利用前缀后缀相同来构造不等式, 找上界下界
s 的最小循环节是 s.len - next
线段树维护哈希
马拉车板子
cin >> n >> s;
t = "$#";
for (int i = 0; i < n; i++) {
t.push_back(s);
t.push_back('#');
}
t.push_back('&');
n = t.size() - 1;
// p 以 c 为中心能扩展的最大步数
// R 最靠右的回文串覆盖区域, C 是 R 的中心
p = 1;
int R = 1, C = 1;
for (int i = 2; i <= n; i++) {
// 如果在覆盖范围内, 先取一个 p 的最小值
if (i <= R)
p = min(p, R - i + 1);
// 向外扩展看看是否可以继续
while (t] == t]) p++;
// 如果比 R 大就更新
if (i + p - 1 >= R)
C = i, R = i + p - 1;
}
int ans = 0;
for (int i = 1; i <= n; i++) {
ans = max(ans, p - 1);
}
cout << ans;
字符串周期
利用 next 数组的含义 (最长相等前后缀)可以知道如果有重叠就会是周期, 判断能否整除即可
while (1) {
cas++;
cin >> n;
if (!n)
break;
cin >> (s + 1);
cout << "Test case #" << cas << '\n';
for (int i = 2; i <= n; i++) {
j = nxt;
while (j && s != s) j = nxt;
if (s == s)
j++;
nxt = j;
if (j * 2 >= i && !(i % (i - j))) {
cout << i << ' ' << (i / (i - j)) << '\n';
}
}
}
字符串大师
通过最小循环节的结论, 求出原来的 nxt 数组
接下来构造, 如果 nxt 大于 0 就跳到前面去, 字符就是那个
图个 nxt 是 0 就往前跳, 把出现的字符都记下来, 当前的填字符是没有出现的字符
cin >> n >> nxt;
s = 'a';
nxt--;
cout << s;
for (int i = 2; i <= n; i++) {
int x;
cin >> x;
nxt = i - x;
if (!nxt) {
// 注意这里要设为 1, 因为位置 1 的 a 不会被算进去 (nxt == 0)
// 为什么 i 的 nxt 值是 0 呢? 是因为不管多长的前缀都不和后缀相等
// 类比 kmp 求法, 每次向前跳, 只要不和 nxt 相等就可以继续等于 0
st = 1;
for (int j = nxt; j; j = nxt) {
st |= (1 << (s - 'a'));
}
for (int j = 0; j < 26; j++) {
if ((st >> j) & 1)
continue;
s = 'a' + j;
break;
}
} else {
s = s];
}
cout << s;
}
动物园
ans = 1;
for (int i = 2, j = 0; i < s.size(); i++) {
// nxt 相当于 i 的父节点, 求 nxt 数组相当于对这个树 dfs
// 由于父节点肯定小于 i, 我们可以在维护栈中的指针 j 指向最大的 x, x*2 <= i
// 指针移动是 O(n) 的
while (j && s != s) j = nxt;
if (s == s)
j++;
while (j * 2 > i) j = nxt;
ans = (ans * (cnt + 1)) % P;
}
P4696 Matching
线段树维护 hash, 支持插入删除, 注意每次加的是增量
P4036 火星人
离线, 搞出每个字符最终的位置, 然后线段树维护 hash, 每次删除节点就把 siz 调为 1 即可
不知怎么的就是调不出来, 80... 鱼油您好，您问了关于字符串问题的一些思考和算法的实现方式，下面我会简洁地逐个进行解答。
### 1. 哈希
哈希用于快速比较字符串或子串的相等性。可以利用前缀哈希和滚动哈希技术在多次比较中节省计算时间。
### 2. KMP算法
- **next数组的构建**：它通过比较前后缀来缩短字符串匹配时间。
- **fail树**：在构建next数组时，实际上是在fail树上进行状态转移。
- **字符串重复结构**：最小循环节可以利用 `s.len - next` 来求得。
### 3. Manacher算法
用于寻找字符串中的最长回文子串。
简单实现步骤如下：
cin >> n >> s;
string t = "$#";
for (int i = 0; i < n; i++) {
t.push_back(s);
t.push_back('#');
}
t.push_back('&');
n = t.size() - 1;
vector<int> p(n, 1);
int R = 1, C = 1;
for (int i = 2; i < n; i++) {
if (i < R) {
p = min(R - i, p);
}
while (t] == t]) {
p++;
}
if (i + p > R) {
R = i + p;
C = i;
}
}
int max_len = 0;
for (int i = 1; i < n - 1; i++) {
max_len = max(max_len, p - 1);
}
cout << max_len << endl;
### 4. 字典树（Trie）：
字典树利用前缀来快速搜索和匹配字符串。特别适用于多模式字符串匹配。
### 5. 线段树和哈希
可以将线段树结合哈希来维护字符串的某些特性，比如快速查询某段子串的哈希值。
希望这些解释能够帮到您解决您遇到的字符串问题。如果有更具体的问题，还请您提供更多信息。
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。 ↑好烦 {:7_113:} 厉害厉害，有没有python版本的 18408238295 发表于 2024-8-26 10:42
厉害厉害，有没有python版本的
算法竞赛基本没 py 吧 柿子饼同学 发表于 2024-8-26 12:07
算法竞赛基本没 py 吧
对的
大比赛基本上没有python {:10_256:}{:10_256:} 看看，学习下{:10_254:} {:10_254:} 谢谢 {:10_280:}{:10_280:}{:10_280:}{:10_280:}{:10_280:}
页:
[1]