文章

27

粉丝

0

获赞

130

访问

8.4k

头像
P1098 前缀字符串 答疑提问:
jsd VIP
P1098 中山大学机试题
发布于2025年2月6日 17:27
阅读数 399

求助这个题,样例好多都无法通过,不知道哪里出了问题

#include<bits/stdc++.h>
using namespace std;

bool compare(string s1, string s2) {
    return s1.size() > s2.size();
}

int main() {
    int n;
    while(cin>>n) {
        if(n == 0) break;
        vector<string> vec;
        for(int i = 1; i <= n; i++) {
            string s;
            cin>>s;
            vec.push_back(s);
        }
        sort(vec.begin(), vec.end(), compare);
        int ans = n;
        vector<int> flag(n, 0);
        for(int i = 0; i < n; i++) {
   ...

登录查看完整内容


登录后发布评论

2 条评论
admin SVIP
2025年2月6日 21:10

该代码在处理字符串时存在逻辑错误,导致某些情况下无法正确排除所有互为前缀的字符串。具体来说,内部循环的条件错误地终止了遍历,导致后面的某些未被标记的字符串未被检查。

错误分析:
原代码中使用了一个while循环来检查后续字符串是否是当前字符串的前缀:

int j = i + 1;
while(j < n && flag[j] == 0) {
    // 检查并标记
    j++;
}

此循环在遇到第一个flag[j] != 0(即已被标记)的字符串时会终止,导致后续未被检查的字符串(即使未被标记)被遗漏。例如,如果有字符串序列A, B(已标记), C(未标记),处理A时会跳过C,导致C未被正确检查。

修正方法:
改用for循环遍历所有后续字符串,仅处理未被标记的项:

for (int j = i + 1; j < n; j++) {
    if (flag[j] == 0) {
        // 检查并标记
    }
}

修正后的代码:

#include<bits/stdc++.h>
using namespace std;

bool compare(string s1, string s2) {
    return s1.size() > s2.size();
}

int main() {
    int n;
    while(cin >> n) {
        if(n == 0) break;
        vector<string> vec;
        for(int i = 0; i < n; i++) {
            string s;
            cin >> s;
            vec.push_back(s);
        }
        sort(vec.begin(), vec.end(), compare);
        int ans = n;
        vector<int> flag(n, 0);
        for(int i = 0; i < n; i++) {
            if (flag[i]) continue; // 跳过已标记的当前字符串
            for(int j = i + 1; j < n; j++) {
                if (flag[j] == 0) {
                    string& s = vec[j];
                    if (vec[i].substr(0, s.size()) == s) {
                        ans--;
                        flag[j] = 1;
                    }
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}

修改说明:

  1. 循环结构更正: 将内部while循环改为for循环,确保遍历所有后续字符串。

  2. 跳过已处理的当前字符串: 在外部循环中,若当前字符串i已被标记,则跳过处理。

  3. 正确标记前缀: 对于每个未被标记的后续字符串j,检查其是否为当前字符串i的前缀,若是则标记j。

此修正确保所有字符串都被正确检查,从而选出满足条件的最大集合。

赞(0)

jsd : 回复 admin: 好详细,感谢感谢!

2025年2月6日 22:31