jjzjj

c++ - 在抛出 'std::bad_alloc' what(): std::bad_alloc 的实例后终止调用

coder 2024-02-07 原文

我的程序中出现了 bad_alloc 异常。

这些是限制条件:

  • 1 <= t=""><=>
  • 每个字符串的长度最多为 100000，并且只包含小写字符。

由于这些限制，我无法弄清楚为什么我的程序得到 bad_alloc。

#include <string>
#include <algorithm>
#include <iostream>
#include <vector>

class SuffixArray {
    std::vector<std::string> suffixes;
    size_t N;
public:
    SuffixArray(std::string& s) {
        N = s.length();
        suffixes.resize(N);
        for (size_t i = 0; i < N; i++)
            suffixes[i] = s.substr(i);
        std::sort(suffixes.begin() , suffixes.end());
    }
    ~SuffixArray() {
    }
    size_t lcp(std::string& s, std::string& t) {
        size_t N = std::min(s.length(), t.length());
        for (size_t i = 0; i < N; i++)
            if (s[i] != t[i]) 
                return i;
        return N;
    }    
};

int main ( int argc, char **argv) {
    int T;
    std::cin >> T;
    std::vector<size_t> results;

    for ( int i = 0; i < T; i++) { 
        std::string str;
        std::cin >> str;
        SuffixArray sa(str);
        size_t sol = 0;

        for ( std::string::iterator it = str.begin(); it != str.end(); ++it) {
            std::string target = std::string(it, str.end());
            sol += sa.lcp(str, target);            
        }
        results.push_back(sol);
    }
    for ( std::vector<size_t>::iterator it = results.begin(); it != results.end(); ++it) 
        std::cout << *it << std::endl;
    results.clear();

    return 0;
}

最佳答案

因为你在这里做了什么:

  for (size_t i = 0; i < N; i++)
        suffixes[i] = s.substr(i);

是:创建N个长度为0,1,2,...,N的子串 这些将消耗的内存总量是:1 + 2 + 3 + ... + N 字节。有了老高斯，你会发现前 N 个数字的总和是:N * (N + 1)/2

现在，如果您设置 N = 100,000，这将导致大约 5GB 的内存消耗 - 这大于最大值。除非您在 64 位系统上运行程序，否则您的程序通常拥有 2GB 地址空间。

编辑:我不知道您要解决的问题是什么，但是您的实现看起来很奇怪:

你永远不会使用计算后缀:你正在使用的 SuffixArray 的唯一函数是 lcp，它没有引用存储的 suffixes vector 。那么，您首先需要它们做什么？

关于c++ - 在抛出 'std::bad_alloc' what(): std::bad_alloc 的实例后终止调用，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/8677238/

ampbad_alloccodestdstringc++stl

有关c++ - 在抛出 'std::bad_alloc' what(): std::bad_alloc 的实例后终止调用的更多相关文章

  1. ruby-on-rails - rails : "missing partial" when calling 'render' in RSpec test - 2

    我正在尝试测试是否存在表单。我是Rails新手。我的new.html.erb_spec.rb文件的内容是:require'spec_helper'describe"messages/new.html.erb"doit"shouldrendertheform"dorender'/messages/new.html.erb'reponse.shouldhave_form_putting_to(@message)with_submit_buttonendendView本身，new.html.erb，有代码:当我运行rspec时，它失败了:1)messages/new.html.erbshou

  2. ruby-on-rails - 'compass watch' 是如何工作的/它是如何与 rails 一起使用的 - 2

    我在我的项目目录中完成了compasscreate.和compassinitrails。几个问题:我已将我的.sass文件放在public/stylesheets中。这是放置它们的正确位置吗？当我运行compasswatch时，它不会自动编译这些.sass文件。我必须手动指定文件:compasswatchpublic/stylesheets/myfile.sass等。如何让它自动运行？文件ie.css、print.css和screen.css已放在stylesheets/compiled。如何在编译后不让它们重新出现的情况下删除它们？我自己编译的.sass文件编译成compiled/t

  3. ruby-on-rails - Rails 3.2.1 中 ActionMailer 中的未定义方法 'default_content_type=' - 2

    我在我的项目中添加了一个系统来重置用户密码并通过电子邮件将密码发送给他，以防他忘记密码。昨天它运行良好(当我实现它时)。当我今天尝试启动服务器时，出现以下错误。=>BootingWEBrick=>Rails3.2.1applicationstartingindevelopmentonhttp://0.0.0.0:3000=>Callwith-dtodetach=>Ctrl-CtoshutdownserverExiting/Users/vinayshenoy/.rvm/gems/ruby-1.9.3-p0/gems/actionmailer-3.2.1/lib/action_mailer

  4. ruby-on-rails - 如何优雅地重启 thin + nginx？ - 2

    我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server

  5. ruby - 在 jRuby 中使用 'fork' 生成进程的替代方案？ - 2

    在MRIRuby中我可以这样做:deftransferinternal_server=self.init_serverpid=forkdointernal_server.runend#Maketheserverprocessrunindependently.Process.detach(pid)internal_client=self.init_client#Dootherstuffwithconnectingtointernal_server...internal_client.post('somedata')ensure#KillserverProcess.kill('KILL',

  6. ruby-on-rails - 如何使用 instance_variable_set 正确设置实例变量？ - 2

    我正在查看instance_variable_set的文档并看到给出的示例代码是这样做的:obj.instance_variable_set(:@instnc_var,"valuefortheinstancevariable")然后允许您在类的任何实例方法中以@instnc_var的形式访问该变量。我想知道为什么在@instnc_var之前需要一个冒号:。冒号有什么作用？ 最佳答案 我的第一直觉是告诉你不要使用instance_variable_set除非你真的知道你用它做什么。它本质上是一种元编程工具或绕过实例变量可见性的黑客攻击

  7. ruby 正则表达式 - 如何替换字符串中匹配项的第 n 个实例 - 2

    在我的应用程序中，我需要能够找到所有数字子字符串，然后扫描每个子字符串，找到第一个匹配范围(例如5到15之间)的子字符串，并将该实例替换为另一个字符串“X”。我的测试字符串s="1foo100bar10gee1"我的初始模式是1个或多个数字的任何字符串，例如，re=Regexp.new(/\d+/)matches=s.scan(re)给出["1","100","10","1"]如果我想用“X”替换第N个匹配项，并且只替换第N个匹配项，我该怎么做？例如，如果我想替换第三个匹配项“10”(匹配项[2])，我不能只说s[matches[2]]="X"因为它做了两次替换“1fooX0barXg

  8. ruby - 主要 :Object when running build from sublime 的未定义方法 `require_relative' - 2

    我已经从我的命令行中获得了一切，所以我可以运行rubymyfile并且它可以正常工作。但是当我尝试从sublime中运行它时，我得到了undefinedmethod`require_relative'formain:Object有人知道我的sublime设置中缺少什么吗？我正在使用OSX并安装了rvm。 最佳答案 或者，您可以只使用“require”，它应该可以正常工作。我认为“require_relative”仅适用于ruby​​1.9+ 关于ruby-主要:Objectwhenrun

  9. ruby - 无法让 RSpec 工作—— 'require' : cannot load such file - 2

    我花了三天的时间用头撞墙，试图弄清楚为什么简单的“rake”不能通过我的规范文件。如果您遇到这种情况:任何文件夹路径中都不要有空格!。严重地。事实上，从现在开始，您命名的任何内容都没有空格。这是我的控制台输出:(在/Users/*****/Desktop/LearningRuby/learn_ruby)$rake/Users/*******/Desktop/LearningRuby/learn_ruby/00_hello/hello_spec.rb:116:in`require':cannotloadsuchfile--hello(LoadError) 最佳

  10. ruby-on-rails - 新 Rails 项目 : 'bundle install' can't install rails in gemfile - 2

    我已经像这样安装了一个新的Rails项目:$railsnewsite它执行并到达:bundleinstall但是当它似乎尝试安装依赖项时我得到了这个错误Gem::Ext::BuildError:ERROR:Failedtobuildgemnativeextension./System/Library/Frameworks/Ruby.framework/Versions/2.0/usr/bin/rubyextconf.rbcheckingforlibkern/OSAtomic.h...yescreatingMakefilemake"DESTDIR="cleanmake"DESTDIR="

随机推荐