文章
27
粉丝
0
获赞
130
访问
8.4k
求助这个题,样例好多都无法通过,不知道哪里出了问题
#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++) {
...
登录后发布评论
该代码在处理字符串时存在逻辑错误,导致某些情况下无法正确排除所有互为前缀的字符串。具体来说,内部循环的条件错误地终止了遍历,导致后面的某些未被标记的字符串未被检查。
错误分析:
原代码中使用了一个while循环来检查后续字符串是否是当前字符串的前缀:
此循环在遇到第一个flag[j] != 0(即已被标记)的字符串时会终止,导致后续未被检查的字符串(即使未被标记)被遗漏。例如,如果有字符串序列A, B(已标记), C(未标记),处理A时会跳过C,导致C未被正确检查。
修正方法:
改用for循环遍历所有后续字符串,仅处理未被标记的项:
修正后的代码:
修改说明:
循环结构更正: 将内部while循环改为for循环,确保遍历所有后续字符串。
跳过已处理的当前字符串: 在外部循环中,若当前字符串i已被标记,则跳过处理。
正确标记前缀: 对于每个未被标记的后续字符串j,检查其是否为当前字符串i的前缀,若是则标记j。
此修正确保所有字符串都被正确检查,从而选出满足条件的最大集合。