Случайная ошибка дамп ядра: ошибка в `./a.out ': free (): недопустимый следующий размер (быстро): 0x00000000010e8d70 *** Прервано (дамп ядра) - PullRequest
Новая
       48

Случайная ошибка дамп ядра: ошибка в `./a.out ': free (): недопустимый следующий размер (быстро): 0x00000000010e8d70 *** Прервано (дамп ядра)

1 голос
/ 21 июня 2020 
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using std::string;

int edit_distance(const string &str1, const string &str2) {
  std::vector<std::vector<int>> strMat(str1.length()+1,std::vector<int>(str2.length(),0));
  
  for(int i=0;i<=str1.length();i++){
    strMat[i][0] = i;
  }
  for(int j=0;j<=str2.length();j++){
    strMat[0][j] = j;
  }
    
  for(int i=1;i<=str1.length();i++){
      for(int j=1;j<=str2.length();j++){
              int min1 = std::min(strMat[i][j-1]+1,strMat[i-1][j]+1);
              int min2;
       
              if(str1[i-1]==str2[j-1]){
                  min2 = std::min(min1,strMat[i-1][j-1]);
              }
              else if(str1[i-1]!=str2[j-1]){
                  min2 = std::min(min1,strMat[i-1][j-1]+1);
              }
              strMat[i][j] = min2;
          }
      }
  
  int ans = strMat[str1.length()][str2.length()]; 
  return ans;
}

int main() {
  string str1;
  string str2;
  std::cin >> str1 >> str2;
  
  std::cout << edit_distance(str1, str2) << std::endl;
  return 0;
}

Я получаю сообщение об ошибке: «***** Ошибка в` ./a.out ': free (): недопустимый следующий размер (быстро): 0x00000000010e8d70 *** Прервано (дамп ядра) ** » случайно на случайных входах. Много раз он работает с одним и тем же входом, а иногда выходит из строя и выдает эту ошибку.

Он дает правильный результат в тех случаях, когда он не выдает ошибку.

1 Ответ

1 голос
/ 21 июня 2020

Что происходит, так это то, что вы выходите за пределы при записи в вектор.

Вы не должны использовать C style [] для доступа к массиву, вместо этого вы должны использовать .at (index), потому что он выполняет проверку границ. 

  std::vector<std::vector<int>> strMat(str1.length()+1,std::vector<int>(str2.length(),0));

Внутренний вектор имеет размер str2.length ()

Здесь вы пишете на 1 элемент сверх его размера. 

 for(int j=0;j<=str2.length();j++){
    strMat[0][j] = j;

У вас такая же проблема: 

  for(int i=1;i<=str1.length();i++){
      for(int j=1;j<=str2.length();j++){ // j <= str2.length() will cause you to access elements in the vector that are outside of its bounds

Также здесь: 

  int ans = strMat[str1.length()][str2.length()];

Поскольку индексирование в c ++ основано на 0, когда вы создаете экземпляр вектора, чтобы иметь место для str2.length ( ), индекс последнего элемента будет иметь значение str2.length () -1

. Вы можете исправить эту проблему, изменив экземпляр вектора на str2.length () + 1 вместо str2. длина (): 

  std::vector<std::vector<int>> strMat(str1.length()+1,std::vector<int>(str2.length()+1,0));
...