[心之碎片] - 字符串

柿子饼同学

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

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

马拉车板子

cin >> n >> s;
t = "$#";
for (int i = 0; i < n; i++) {
    t.push_back(s[i]);
    t.push_back('#');
}
t.push_back('&');
n = t.size() - 1;

// p[c] 以 c 为中心能扩展的最大步数
// R 最靠右的回文串覆盖区域, C 是 R 的中心
p[1] = 1;
int R = 1, C = 1;
for (int i = 2; i <= n; i++) {
    // 如果在覆盖范围内, 先取一个 p 的最小值
    if (i <= R)
        p[i] = min(p[C * 2 - i], R - i + 1);
    // 向外扩展看看是否可以继续
    while (t[i + p[i]] == t[i - p[i]]) p[i]++;
    // 如果比 R 大就更新
    if (i + p[i] - 1 >= R)
        C = i, R = i + p[i] - 1;
}

int ans = 0;
for (int i = 1; i <= n; i++) {
    ans = max(ans, p[i] - 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[i - 1];
        while (j && s[j + 1] != s[i]) j = nxt[j];
        if (s[j + 1] == s[i])
            j++;
        nxt[i] = j;

        if (j * 2 >= i && !(i % (i - j))) {
            cout << i << ' ' << (i / (i - j)) << '\n';
        }
    }
}

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

cin >> n >> nxt[1];
s[1] = 'a';
nxt[1]--;
cout << s[1];
for (int i = 2; i <= n; i++) {
    int x;
    cin >> x;
    nxt[i] = i - x;

    if (!nxt[i]) {
        // 注意这里要设为 1, 因为位置 1 的 a 不会被算进去 (nxt[1] == 0)
        // 为什么 i 的 nxt 值是 0 呢? 是因为不管多长的前缀都不和后缀相等
        // 类比 kmp 求法, 每次向前跳, 只要不和 nxt[j] 相等就可以继续等于 0
        st = 1;
        for (int j = nxt[i - 1]; j; j = nxt[j]) {
            st |= (1 << (s[j + 1] - 'a'));
        }
        for (int j = 0; j < 26; j++) {
            if ((st >> j) & 1)
                continue;
            s[i] = 'a' + j;
            break;
        }
    } else {
        s[i] = s[nxt[i]];
    }
    cout << s[i];
}

动物园

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

    ans = (ans * (cnt[j] + 1)) % P;
}

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算法
用于寻找字符串中的最长回文子串。
简单实现步骤如下：

cin >> n >> s;
string t = "$#";
for (int i = 0; i < n; i++) {
    t.push_back(s[i]);
    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[i] = min(R - i, p[2 * C - i]);
    }
    while (t[i + p[i]] == t[i - p[i]]) {
        p[i]++;
    }
    if (i + p[i] > R) {
        R = i + p[i];
        C = i;
    }
}

int max_len = 0;
for (int i = 1; i < n - 1; i++) {
    max_len = max(max_len, p[i] - 1);
}

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