прекращение вызова после выброса экземпляра 'std :: bad_alloc' what (): std :: bad_alloc Прервано

Question

Я получаю исключение bad_alloc в моей программе.

Это ограничения:

• 1 <= T <= 10 </li>
• Длина каждой строки не более 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;
}

Answer 1

Потому что вы здесь делаете:

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

is: Создать N подстроки длиной 0, 1, 2, ..., N Общий объем памяти, который они будут использовать: 1 + 2 + 3 + ... + N байт. Имея в руках старого доброго Гаусса, вы обнаружите, что сумма первых N чисел равна: N * (N + 1) / 2

Теперь, если вы установите N = 100000, это приведет к примерно 5 ГБ потребления памяти - что больше, чем макс. 2 ГБ адресного пространства, которое обычно имеется в вашей программе, если только вы не запускаете ее в 64-битной системе.

Редактировать : Я не знаю, в чем заключается проблема, которую вы пытаетесь решить, однако ваша реализация кажется странной:

Вы никогда не используете вычисленные суффиксы: единственная используемая вами функция SuffixArray - это lcp, которая не ссылается на сохраненный вектор suffixes. Так зачем они вам нужны?