自动搬运

查看原文

来自洛谷，原作者为

	RyanLi 跟着光，靠近光，成为光，散发光。

搬运于2025-08-24 21:16:07，当前版本为作者最后更新于2024-03-11 14:09:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Source & Knowledge

2024 年 3 月语言月赛，由洛谷网校入门计划/基础计划提供。

题目大意

现代 szm 语采用罗马字表示，其划分音节的规则如下：

• 规定元音是字符 a、e、i、o、u 之一。
• 一般地，一个音节仅包含一个元音，并且以元音结尾。
• 特别地，当且仅当 n 后第一个字符不是元音时，n 单独作一个音节。
• 一个音节至多包含 $3$ 个字符。

将字符串 $S$ 的 $k$ 个音节依次表示为 $S'_1 \sim S'_k$，将另一个字符串 $T$ 的 $m$ 个音节依次表示为 $T'_1 \sim T'_m$。

如果存在一个正整数 $p$，满足 $p+m-1 \leq k$ 且对于从 $p$ 到 $p+m-1$ 的每个正整数 $i$ 都有 $S'_i=T'_{i - p + 1}$，那么称 $S$「包含」$T$。

在 szm 语中有一些习语，一种习语对应有一些固定的字符串。如果一个字符串「包含」且仅「包含」一种习语的一个固定子串，那么这个字符串是这种习语。

某种习语对应 $n$ 个子串，给定 $q$ 个字符串，判断每个字符串是否是这种习语。

题目分析

注意到，询问的 $q$ 个字符串的字符个数不超过 $5 \times 10^5$。我们需要在被询问的字符串中匹配这种习语的子串，对于这样的数据范围，直接使用字符串查找子串函数 s.find() 即可。

但是，szm 语允许单个元音构成一个音节。如果出现例如子串为 a，而查找到的位置的音节为 za，那么此时就会产生错误的匹配，导致答案错误。

我们设询问的字符串为 $s$，查找到的位置（在 $s$ 中的下标）为 $pos$。那么如果 $pos \ne 0$，而且 $s_{pos}$ 是元音，那么就需要判断 $s_{pos - 1}$ 是否为辅音。如果为辅音，那么就可以和 $s_{pos}$ 组成一个音节，那么当前位置就无法完成匹配，需要继续向后查找。

为了缩短代码，可以编写如下函数，用于判断字符 $c$ 是否为元音。

bool vowel(char c) {
    return c == 'a' || c == 'i' || c == 'u' || c == 'e' || c == 'o';
}

同样地，由于 szm 语允许 n 单独构成一个音节，因此我们还需要判断匹配到的子串的末尾位置 $pos'$ 是否为字符 n。如果是，并且 $pos'$ 不是 $s$ 的末尾位置，那么就需要判断 $s_{pos' + 1}$ 是否为元音。

如果 $s_{pos'}$ 是 n 且 $s_{pos' + 1}$ 不存在或不为元音，或者 $s_{pos'}$ 不为 n，那么说明匹配成功，就给匹配数加一，然后跳出循环，匹配下一个子串。

在匹配完所有子串后，如果只有一个子串成功匹配，那么表明这个字符串是这种习语，输出 Yes, Commander，否则输出 No, Commander。

cin >> n >> q;
for (int i = 1; i <= n; ++i) cin >> a[i];
while (q--) {
    cnt = 0;
    cin >> s;
    for (int i = 1; i <= n; ++i) {
        pos = s.find(a[i]);
        if (pos == s.npos) continue;
        while (pos != s.npos) {
            if ((vowel(s[pos]) && pos && !vowel(s[pos - 1])) || (!vowel(s[pos]) && pos && !vowel(s[pos - 1]) && s[pos - 1] != 'n')) {
                pos = s.find(a[i], pos + 1);
                continue;
            } if ((s[pos + a[i].size() - 1] == 'n' && (pos + a[i].size() >= s.size() || (pos + a[i].size() < s.size() && !vowel(s[pos + a[i].size()])))) || s[pos + a[i].size() - 1] != 'n') {
                ++cnt;
                break;
            } pos = s.find(a[i], pos + 1);
        }
    } cout << (cnt == 1 ? "Yes, Commander\n" : "No, Commander\n");
}

完整代码

#include <iostream>
using namespace std;

const int N = 15;
int n, q, cnt, pos;
string a[N], s;
bool flag;

bool vowel(char c) {
    return c == 'a' || c == 'i' || c == 'u' || c == 'e' || c == 'o';
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cin >> n >> q;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    while (q--) {
        cnt = 0;
        cin >> s;
        for (int i = 1; i <= n; ++i) {
            pos = s.find(a[i]);
            if (pos == s.npos) continue;
            while (pos != s.npos) {
                if ((vowel(s[pos]) && pos && !vowel(s[pos - 1])) || (!vowel(s[pos]) && pos && !vowel(s[pos - 1]) && s[pos - 1] != 'n')) {
                    pos = s.find(a[i], pos + 1);
                    continue;
                } if ((s[pos + a[i].size() - 1] == 'n' && (pos + a[i].size() >= s.size() || (pos + a[i].size() < s.size() && !vowel(s[pos + a[i].size()])))) || s[pos + a[i].size() - 1] != 'n') {
                    ++cnt;
                    break;
                } pos = s.find(a[i], pos + 1);
            }
        } cout << (cnt == 1 ? "Yes, Commander\n" : "No, Commander\n");
    } return 0;
}