C++ : terminate called after throwing an instance of 'std::bad_alloc' while computing length of big strings

Question

在下面的代码中，我试图计算输入字符串 s 中 a 的数量，重复字符串(如果需要)最多 n 个位置，其中 0 < n < 10^(12)。我的代码适用于较小的 n 值，但它为较大的 n 值提供 std::bad_alloc() 。这是我的代码:

#include <string>
#include <iostream>


using namespace std;


int main(){
    string s;
    cin >> s;
    long n;
    cin >> n;
    long len = s.length();
    long ans = 0;
    if(n <= len){
        for(long i = 0; i < n; i++){
            if(s[i] == 'a'){
                ans++;
            }   
        }
    }
    else{
        string comp = s;
        while(comp.length() < n){
            comp += s;
        }
        long diff = comp.length() - n;
        if(diff > 0){
            while (diff == 0){
                comp.pop_back();
                diff = comp.length() - n;
            }
        }
        for(long i = 0; i < n; i++){
            if(comp[i] == 'a'){
                ans++;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Answer 1

10^12 是一个巨大的数字。即使每个项目占用 1 个字节，您也需要 1 TB 的内存。

让我们改变策略。查看下一个示例:

instance

对于 n = word.size()，这将返回 1。

如果 n = 2*word.size():

instanceinstance

这将返回 2:

对于 n = 3*word.size():

instanceinstanceinstance

这将返回 3:

看到这里的模式了吗？你可以用一个简单的乘法得到结果，然后用一个简单的循环得到其余的:

std::string name;
std::cin >> name;

int n;
std::cin >> n;

int multiplier = std::count(name.begin(),name.end(),'a');

int full_iterations = n / name.size();
int last_iteration = n % name.size();

int ocurrences = multiplier * full_iterations * std::count(name.begin(),name.begin() + last_iteration,'a');

std::cout << ocurrences << std::endl;

std::count 的文档 right here