[心之碎片] - 字符串

柿子饼同学

包括 :
哈希, manacher, 字典树, KMP

一些思考:
字符串题首先想哈希
kmp 的求 next 数组过程其实是在 fail 树上的遍历
要善用 next 数组的前后缀相等性质
判断长字符串想倍增比较
利用前缀后缀相同来构造不等式, 找上界下界
s 的最小循环节是 s.len - next[s.len]
线段树维护哈希

马拉车板子

1. cin >> n >> s;
   
2. t = "$#";
   
3. for (int i = 0; i < n; i++) {
   
4.     t.push_back(s[i]);
   
5.     t.push_back('#');
   
6. }
   
7. t.push_back('&');
   
8. n = t.size() - 1;
   
9. 
   
10. // p[c] 以 c 为中心能扩展的最大步数
    
11. // R 最靠右的回文串覆盖区域, C 是 R 的中心
    
12. p[1] = 1;
    
13. int R = 1, C = 1;
    
14. for (int i = 2; i <= n; i++) {
    
15.     // 如果在覆盖范围内, 先取一个 p 的最小值
    
16.     if (i <= R)
    
17.         p[i] = min(p[C * 2 - i], R - i + 1);
    
18.     // 向外扩展看看是否可以继续
    
19.     while (t[i + p[i]] == t[i - p[i]]) p[i]++;
    
20.     // 如果比 R 大就更新
    
21.     if (i + p[i] - 1 >= R)
    
22.         C = i, R = i + p[i] - 1;
    
23. }
    
24. 
    
25. int ans = 0;
    
26. for (int i = 1; i <= n; i++) {
    
27.     ans = max(ans, p[i] - 1);
    
28. }
    
29. cout << ans;

复制代码

字符串周期
利用 next 数组的含义 (最长相等前后缀)可以知道如果有重叠就会是周期, 判断能否整除即可

1. while (1) {
   
2.     cas++;
   
3.     cin >> n;
   
4.     if (!n)
   
5.         break;
   
6.     cin >> (s + 1);
   
7. 
   
8.     cout << "Test case #" << cas << '\n';
   
9.     for (int i = 2; i <= n; i++) {
   
10.         j = nxt[i - 1];
    
11.         while (j && s[j + 1] != s[i]) j = nxt[j];
    
12.         if (s[j + 1] == s[i])
    
13.             j++;
    
14.         nxt[i] = j;
    
15. 
    
16.         if (j * 2 >= i && !(i % (i - j))) {
    
17.             cout << i << ' ' << (i / (i - j)) << '\n';
    
18.         }
    
19.     }
    
20. }

复制代码

字符串大师
通过最小循环节的结论, 求出原来的 nxt 数组
接下来构造, 如果 nxt 大于 0 就跳到前面去, 字符就是那个
图个 nxt 是 0 就往前跳, 把出现的字符都记下来, 当前的填字符是没有出现的字符

1. cin >> n >> nxt[1];
   
2. s[1] = 'a';
   
3. nxt[1]--;
   
4. cout << s[1];
   
5. for (int i = 2; i <= n; i++) {
   
6.     int x;
   
7.     cin >> x;
   
8.     nxt[i] = i - x;
   
9. 
   
10.     if (!nxt[i]) {
    
11.         // 注意这里要设为 1, 因为位置 1 的 a 不会被算进去 (nxt[1] == 0)
    
12.         // 为什么 i 的 nxt 值是 0 呢? 是因为不管多长的前缀都不和后缀相等
    
13.         // 类比 kmp 求法, 每次向前跳, 只要不和 nxt[j] 相等就可以继续等于 0
    
14.         st = 1;
    
15.         for (int j = nxt[i - 1]; j; j = nxt[j]) {
    
16.             st |= (1 << (s[j + 1] - 'a'));
    
17.         }
    
18.         for (int j = 0; j < 26; j++) {
    
19.             if ((st >> j) & 1)
    
20.                 continue;
    
21.             s[i] = 'a' + j;
    
22.             break;
    
23.         }
    
24.     } else {
    
25.         s[i] = s[nxt[i]];
    
26.     }
    
27.     cout << s[i];
    
28. }

复制代码

动物园

1. ans = 1;
   
2. for (int i = 2, j = 0; i < s.size(); i++) {
   
3.     // nxt[i] 相当于 i 的父节点, 求 nxt 数组相当于对这个树 dfs
   
4.     // 由于父节点肯定小于 i, 我们可以在维护栈中的指针 j 指向最大的 x, x*2 <= i
   
5.     // 指针移动是 O(n) 的
   
6.     while (j && s[i] != s[j + 1]) j = nxt[j];
   
7.     if (s[j + 1] == s[i])
   
8.         j++;
   
9.     while (j * 2 > i) j = nxt[j];
   
10. 
    
11.     ans = (ans * (cnt[j] + 1)) % P;
    
12. }

复制代码

P4696 [CEOI2011] Matching
线段树维护 hash, 支持插入删除, 注意每次加的是增量
P4036 [JSOI2008] 火星人
离线, 搞出每个字符最终的位置, 然后线段树维护 hash, 每次删除节点就把 siz 调为 1 即可
不知怎么的就是调不出来, 80...

FishC

鱼油您好，您问了关于字符串问题的一些思考和算法的实现方式，下面我会简洁地逐个进行解答。

### 1. 哈希
哈希用于快速比较字符串或子串的相等性。可以利用前缀哈希和滚动哈希技术在多次比较中节省计算时间。

### 2. KMP算法
- **next数组的构建**：它通过比较前后缀来缩短字符串匹配时间。
- **fail树**：在构建next数组时，实际上是在fail树上进行状态转移。
- **字符串重复结构**：最小循环节可以利用 `s.len - next[s.len-1]` 来求得。

### 3. Manacher算法
用于寻找字符串中的最长回文子串。
简单实现步骤如下：

1. cin >> n >> s;
   
2. string t = "$#";
   
3. for (int i = 0; i < n; i++) {
   
4.     t.push_back(s[i]);
   
5.     t.push_back('#');
   
6. }
   
7. t.push_back('&');
   
8. n = t.size() - 1;
   
9. 
   
10. vector<int> p(n, 1);
    
11. int R = 1, C = 1;
    
12. 
    
13. for (int i = 2; i < n; i++) {
    
14.     if (i < R) {
    
15.         p[i] = min(R - i, p[2 * C - i]);
    
16.     }
    
17.     while (t[i + p[i]] == t[i - p[i]]) {
    
18.         p[i]++;
    
19.     }
    
20.     if (i + p[i] > R) {
    
21.         R = i + p[i];
    
22.         C = i;
    
23.     }
    
24. }
    
25. 
    
26. int max_len = 0;
    
27. for (int i = 1; i < n - 1; i++) {
    
28.     max_len = max(max_len, p[i] - 1);
    
29. }
    
30. 
    
31. cout << max_len << endl;

复制代码

### 4. 字典树（Trie）：
字典树利用前缀来快速搜索和匹配字符串。特别适用于多模式字符串匹配。

### 5. 线段树和哈希
可以将线段树结合哈希来维护字符串的某些特性，比如快速查询某段子串的哈希值。

希望这些解释能够帮到您解决您遇到的字符串问题。如果有更具体的问题，还请您提供更多信息。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

sfqxx

↑好烦

很cool的阳

18408238295

厉害厉害，有没有python版本的

柿子饼同学

18408238295 发表于 2024-8-26 10:42
厉害厉害，有没有python版本的

算法竞赛基本没 py 吧

zsy0226

柿子饼同学 发表于 2024-8-26 12:07
算法竞赛基本没 py 吧

对的
大比赛基本上没有python

简柠啦

trinityee

看看，学习下

磷酸

森林格格屋

谢谢

cc885544