B3950 题解

· · 题解

Source & Knowledge

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

题目大意

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

将字符串 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;
}