时间戳

首页 > 解决方案 > 在 CCC 分级机中接收信号 6，2020 s3 搜索字符串

c++ - 在 CCC 分级机中接收信号 6，2020 s3 搜索字符串

问题描述

加拿大计算机竞赛：2020 年第 1 阶段，高级 #3 给你一个字符串 N，称为 needle 和一个字符串 H，称为 haystack，两者都只包含小写字母 a..z。

编写一个程序来计算 N 的不同排列的数量，这些排列至少出现一次 H 的子串。请注意，N 可以介于 1 和 |N| 之间！总共有不同的排列——例如，字符串 aab 有 3 个不同的排列（aab、aba 和 baa）。

问题：我的程序在测试用例 1-113 上运行得非常好，但无论我如何修改我的程序，CCC 分级器总是在测试用例 114 处显示接收信号 6 。

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

int alpha_a[26], alpha_b[26];

bool check() {
    for (int i = 0; i < 26; ++i) {
        if (alpha_a[i] != alpha_b[i]) {
            return false;
        }
    }
    return true;
}
int main() {
    string a, b;
    cin >> a >> b;
    if (b.size() < a.size()) {
        cout << "0" << endl;
        return 0;
    }
    memset(alpha_a, 0, 26);
    memset(alpha_b, 0, 26);
    for (int i = 0; i < a.size(); ++i) {
        ++alpha_a[a[i] - 'a'];
        ++alpha_b[b[i] - 'a'];
    }
    string process = b.substr(0, a.size());
    set<string> no_repetition = {};
    int begin = 0, end = a.size();
    for (; end != b.size(); ++end, ++begin) {
        if (check()) {
            no_repetition.emplace(process);
        }
        process.erase(0, 1);
        --alpha_b[b[begin] - 'a'];
        process += b[end];
        ++alpha_b[b[end] - 'a'];
    }
    if (check()) {
        no_repetition.emplace(process);
    }
    cout << no_repetition.size() << endl;
    return 0;
}

标签： c++

解决方案

此错误消息很可能是因为您不断将每个排列的副本添加到no_repetition向量中，最终耗尽了评分者的内存并导致std::bad_alloc被抛出；这个异常没有被捕获，并且一个未捕获的异常导致std::terminate被调用，它调用abort，它以 终止程序SIGABRT，它通常具有信号编号6。

要在这个问题上获得满分，您需要找到一种方法来对排列进行重复数据删除，而无需将每个排列的副本存储在集合中。

推荐阅读