It's Mooin' Time

题意

给定一个长度为 $N$ 的小写字母串。一个 moo 是形如 abb 的长度为 3 的字符串，其中 $a != b$ 。

如果某种 moo 在原始字符串中出现至少 $F$ 次，就可能是答案。

但输入字符串可能有至多一个字符损坏，所以可以选择不改，或把某一个位置改成任意小写字母。求所有可能达到出现次数至少 $F$ 的 moo，并按字典序输出。

思路

先看一个直接枚举的暴力：

cpp

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
60
61
62
63
64
65
66
67
68
69
70
71/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 15:38
 * update_at: 2026-07-11 15:41
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int C = 26;

int n, f;
string s;
bool possible[C][C]; // possible[a][b] 表示 abb 可以达到频次要求。

bool is_moo_string(const string &t, int pos) {
    if (pos < 0 || pos + 2 >= (int)t.size()) return false;
    return t[pos] != t[pos + 1] && t[pos + 1] == t[pos + 2];
}

void check_string(const string &t) {
    int cnt[C][C];
    memset(cnt, 0, sizeof(cnt));

    for (int i = 0; i + 2 < (int)t.size(); i++) {
        if (!is_moo_string(t, i)) continue;

        int a = t[i] - 'a';
        int b = t[i + 1] - 'a';
        cnt[a][b]++;
        if (cnt[a][b] >= f) {
            possible[a][b] = true;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> f;
    cin >> s;

    // 小数据暴力：枚举改哪一个位置、改成哪个字符，再完整重新统计所有 moo。
    for (int pos = 0; pos < n; pos++) {
        string t = s;
        for (char c = 'a'; c <= 'z'; c++) {
            t[pos] = c;
            check_string(t);
        }
    }

    int total = 0;
    for (int a = 0; a < C; a++) {
        for (int b = 0; b < C; b++) {
            if (a != b && possible[a][b]) total++;
        }
    }

    cout << total << '\n';
    for (int a = 0; a < C; a++) {
        for (int b = 0; b < C; b++) {
            if (a == b || !possible[a][b]) continue;
            cout << char('a' + a) << char('a' + b) << char('a' + b) << '\n';
        }
    }

    return 0;
}

这个暴力枚举修改位置和替换字符，每次完整扫描字符串统计 moo。它很直接，但复杂度是 $O(26N^2)$ 。

关键观察：修改一个位置 pos，只会影响包含它的长度为 3 的子串。

这些子串的起点只可能是：

text

1pos-2, pos-1, pos

也就是说，每次修改最多影响 3 个子串。

我们维护当前字符串中每种 moo 的出现次数 occ[a][b]，其中 abb 是 moo。

枚举一个位置时：

先删除旧字符串中受影响的 3 个子串贡献。
枚举把这个位置改成 a..z。
加入新字符串中受影响的 3 个子串贡献。
如果某种 moo 的计数达到 $F$ ，把它记入答案。
撤销这次替换，继续尝试下一个字符。
最后恢复原字符和旧贡献。

这样每次尝试只做常数次更新。

代码

cpp

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 15:38
 * update_at: 2026-07-11 15:41
 */
#include <bits/stdc++.h>
using namespace std;

const int C = 26;

int n, f;
string s;
int occ[C][C];       // occ[a][b] 表示当前字符串中 abb 的出现次数。
bool possible[C][C]; // possible[a][b] 表示 abb 可能是答案。

bool is_moo_at(int pos) {
    if (pos < 0 || pos + 2 >= n) return false;
    if (s[pos] == s[pos + 1]) return false;
    if (s[pos + 1] != s[pos + 2]) return false;
    return true;
}

void update_at(int pos, int delta) {
    if (!is_moo_at(pos)) return;

    int a = s[pos] - 'a';
    int b = s[pos + 1] - 'a';

    occ[a][b] += delta;
    if (occ[a][b] >= f) {
        possible[a][b] = true;
    }
}

void update_around(int pos, int delta) {
    // 修改 pos 只会影响以 pos-2、pos-1、pos 开始的三个长度为 3 的子串。
    update_at(pos - 2, delta);
    update_at(pos - 1, delta);
    update_at(pos, delta);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> f;
    cin >> s;

    for (int i = 0; i + 2 < n; i++) {
        update_at(i, 1);
    }

    for (int i = 0; i < n; i++) {
        char old = s[i];

        update_around(i, -1);
        for (char c = 'a'; c <= 'z'; c++) {
            s[i] = c;
            update_around(i, 1);
            update_around(i, -1);
        }
        s[i] = old;
        update_around(i, 1);
    }

    int total = 0;
    for (int a = 0; a < C; a++) {
        for (int b = 0; b < C; b++) {
            if (a != b && possible[a][b]) total++;
        }
    }

    cout << total << '\n';
    for (int a = 0; a < C; a++) {
        for (int b = 0; b < C; b++) {
            if (a == b || !possible[a][b]) continue;
            cout << char('a' + a) << char('a' + b) << char('a' + b) << '\n';
        }
    }

    return 0;
}

复杂度

枚举 $N$ 个位置和 26 个替换字符，每次只更新常数个子串。

时间复杂度为 $O(26N)$ ，空间复杂度为 $O(1)$ 。

总结

字符串修改题常见技巧是先看“一个修改会影响哪些局部结构”。

本题局部结构长度为 3，所以一次修改只影响最多三个子串，增量维护计数即可。

目录

题意

思路

代码

复杂度

总结