Uddered but not Herd

题意

给定牛文字母表的顺序，以及 Farmer John 听到的一串字母。

Bessie 会一遍一遍完整唱这个字母表，Farmer John 可能漏听其中一些字母。求至少唱了几遍，才能让听到的字符串成为这些歌声的子序列。

思路

暴力想法

可以枚举 Bessie 唱了几遍，把多遍 cowphabet 拼起来，然后判断听到的字符串是否是它的子序列：

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/**
 * 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 13:40
 * update_at: 2026-07-11 13:44
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

bool can_hear(string alphabet, string heard, int times) {
    string hummed = "";
    for (int i = 1; i <= times; i++) {
        hummed += alphabet;
    }

    int p = 0;
    for (int i = 0; i < (int)hummed.size() && p < (int)heard.size(); i++) {
        if (hummed[i] == heard[p]) {
            p++;
        }
    }
    return p == (int)heard.size();
}

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

    string alphabet, heard;
    cin >> alphabet >> heard;

    // 最坏每听到一个字母都需要新唱一遍，所以答案不超过 heard 的长度。
    for (int times = 1; times <= (int)heard.size(); times++) {
        if (can_hear(alphabet, heard, times)) {
            cout << times << '\n';
            return 0;
        }
    }

    return 0;
}

这种方法符合题意，但还可以更直接。

统计断点

记录每个字母在 cowphabet 中的位置。

在同一遍 cowphabet 里，听到的字母位置必须严格递增。如果相邻两个听到的字母满足：

text

1pos[heard[i]] <= pos[heard[i-1]]

说明第 i 个字母不能继续放在当前这一遍中，必须开启下一遍。

所以答案就是：

text

11 + 位置序列中非递增断点的数量

样例中 cowphabet 是普通顺序，mood 的位置变化为：

text

1
2
3m -> o 递增
o -> o 不递增，开启新一遍
o -> d 倒退，开启新一遍

所以答案是 3。

代码

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/**
 * 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 13:40
 * update_at: 2026-07-11 13:44
 */
#include <bits/stdc++.h>
using namespace std;

int pos[26]; // pos[c] 表示字母 c 在牛文字母表中的位置。

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

    string alphabet, heard;
    cin >> alphabet >> heard;

    for (int i = 0; i < 26; i++) {
        pos[alphabet[i] - 'a'] = i;
    }

    int answer = 1;
    for (int i = 1; i < (int)heard.size(); i++) {
        int last_pos = pos[heard[i - 1] - 'a'];
        int now_pos = pos[heard[i] - 'a'];

        // 当前字母没有出现在上一字母之后，必须开始下一遍字母歌。
        if (now_pos <= last_pos) {
            answer++;
        }
    }

    cout << answer << '\n';

    return 0;
}

复杂度

设听到的字符串长度为 $M$ ，时间复杂度为 $O(M)$ 。

使用长度为 26 的位置数组，空间复杂度为 $O(1)$ 。

总结

这题的关键是把自定义字母表转成位置数组。

同一遍字母歌内部，听到的字母位置必须严格递增；每出现一次不递增，就必须多唱一遍。

目录

题意

思路

暴力想法

统计断点

代码

复杂度

总结