Ошибка сегментации алгоритма поиска слов

Question

Я долгое время работал над алгоритмом поиска слов, я думаю, что сделал это хорошо и решил проверить пределы. Я создал программу, которая делает файл настолько большим, насколько я хочу. Поэтому я сделал матрицу 10000 * 10000 (10000000 букв) и действительно длинное слово из верхнего левого угла в нижний правый угол. Дело в том, что он работает с матрицей 4000 * 4000, но потом он становится больше, он просто падает. Я попытался прокомментировать все остальные проверки для возможного местоположения и оставил правый, и он отлично работает даже с матрицей 10000 * 10000, но как только я добавляю другие проверки, он останавливается, и я понятия не имею, почему. Какие-либо предложения?

Моего код:

#include <iostream>  //Might Be: 
    #include <string>  // <-----> 
    #include <fstream>  // /-\ (1)/\    /\(3) 
    #include <new>   // |  \    /
    #include <cstdlib>  // |  \   /
          // |   \   /
          // |   \  /
          // |   \  /
          // \_/  (2)\/  \/(4) 
          // 

    using namespace std; 
             //Loop[4] //Loop[5] 
    int * Possibles(int Widht, int Height, int Poz, int Poz1, int Leng, int * Possible) 
    { 
     if(Poz1 < Widht - Leng + 1) // To right 
     { 
      Possible[0] = 1; 
     } 

     if(Poz1 >= Leng - 1) // To left 
     { 
      Possible[1] = 1; 
     } 

     if(Poz <= Height - Leng) // From top to bottom 
     { 
      Possible[2] = 1; 
     } 

     if(Poz >= Leng) // From bottom to top 
     { 
      Possible[3] = 1; 
     } 

     if(Poz + Leng <= Height && Poz1 + Leng <= Widht) //(2) 
     { 
      Possible[4] = 1; 
     } 

     if(Poz + Leng <= Height && Poz1 - Leng + 1 >= 0) //(4) 
     { 
      Possible[5] = 1; 
     } 

     if(Poz - Leng + 1 >= 0 && Poz1 - Leng + 1 >= 0) //(1) 
     { 
      Possible[6] = 1; 
     } 

     if(Poz - Leng + 1 >= 0 && Poz1 + Leng <= Widht) //(3) 
     { 
      Possible[7] = 1; 
     } 

     return Possible; 
    } 

    int * Zero(int * Possible) 
    { 
      Possible[0] = 0; 
      Possible[1] = 0; 
      Possible[2] = 0; 
      Possible[3] = 0; 
      Possible[4] = 0; 
      Possible[5] = 0; 
      Possible[6] = 0; 
      Possible[7] = 0; 

      return Possible; 
    } 

    string Next(string * NewMatrix, int Height, int Widht) 
    { 
     return NewMatrix[Height].substr(Widht, 1); 
    } 

    bool Find(string Word, int Poz, int Poz1, int Look, string Have, string * Matrix, int * Possible, int Backup, int Backup1) 
    { 
     if(Have == Word) 
     { 
      return true; 
      return Possible; 
     } 

     string NewLet = Word.substr(Look, 1); 

     if(Possible[0] == 1) 
     { 
      if(NewLet == Next(Matrix, Poz, Poz1 + 1)) 
      { 
       Have += NewLet; 

       return Find(Word, Poz, Poz1 + 1, Look + 1, Have, Matrix, Possible, Backup, Backup1); 
      } 
      else 
      { 
       Possible[0] = 0; 
       Have = Word.substr(0, 1); 

       return Find(Word, Backup, Backup1, 1, Have, Matrix, Possible, Backup, Backup1); 
      } 
     } 

     if(Possible[1] == 1) 
     { 
      if(NewLet == Next(Matrix, Poz, Poz1 - 1)) 
      { 
       Have += NewLet; 

       return Find(Word, Poz, Poz1 - 1, Look + 1, Have, Matrix, Possible, Backup, Backup1); 
      } 
      else 
      { 
       Possible[1] = 0; 
       Have = Word.substr(0, 1); 

       return Find(Word, Backup, Backup1, 1, Have, Matrix, Possible, Backup, Backup1); 
      } 
     } 

     if(Possible[2] == 1) 
     { 
      if(NewLet == Next(Matrix, Poz + 1, Poz1)) 
      { 
       Have += NewLet; 

       return Find(Word, Poz + 1, Poz1, Look + 1, Have, Matrix, Possible, Backup, Backup1); 
      } 
      else 
      { 
       Possible[2] = 0; 
       Have = Word.substr(0, 1); 

       return Find(Word, Backup, Backup1, 1, Have, Matrix, Possible, Backup, Backup1); 
      } 
     } 

     if(Possible[3] == 1) 
     { 
      if(NewLet == Next(Matrix, Poz - 1, Poz1)) 
      { 
       Have += NewLet; 

       return Find(Word, Poz - 1, Poz1, Look + 1, Have, Matrix, Possible, Backup, Backup1); 
      } 
      else 
      { 
       Possible[3] = 0; 
       Have = Word.substr(0, 1); 

       return Find(Word, Backup, Backup1, 1, Have, Matrix, Possible, Backup, Backup1); 
      } 
     } 

     if(Possible[4] == 1) 
     { 
      if(NewLet == Next(Matrix, Poz + 1, Poz1 + 1)) 
      { 
       Have += NewLet; 

       return Find(Word, Poz + 1, Poz1 + 1, Look + 1, Have, Matrix, Possible, Backup, Backup1); 
      } 
      else 
      { 
       Possible[4] = 0; 
       Have = Word.substr(0, 1); 

       return Find(Word, Backup, Backup1, 1, Have, Matrix, Possible, Backup, Backup1); 
      } 
     } 

     if(Possible[5] == 1) 
     { 
      if(NewLet == Next(Matrix, Poz + 1, Poz1 - 1)) 
      { 
       Have += NewLet; 

       return Find(Word, Poz + 1, Poz1 - 1, Look + 1, Have, Matrix, Possible, Backup, Backup1); 
      } 
      else 
      { 
       Possible[5] = 0; 

       Have = Word.substr(0, 1); 

       return Find(Word, Backup, Backup1, 1, Have, Matrix, Possible, Backup, Backup1); 
      } 
     } 

     if(Possible[6] == 1) 
     { 
      if(NewLet == Next(Matrix, Poz - 1, Poz1 - 1)) 
      { 
       Have += NewLet; 

       return Find(Word, Poz - 1, Poz1 - 1, Look + 1, Have, Matrix, Possible, Backup, Backup1); 
      } 
      else 
      { 
       Possible[6] = 0; 
       Have = Word.substr(0, 1); 

       return Find(Word, Backup, Backup1, 1, Have, Matrix, Possible, Backup, Backup1); 
      } 
     } 

     if(Possible[7] == 1) 
     { 
      if(NewLet == Next(Matrix, Poz - 1, Poz1 + 1)) 
      { 
       Have += NewLet; 

       return Find(Word, Poz - 1, Poz1 + 1, Look + 1, Have, Matrix, Possible, Backup, Backup1); 
      } 
      else 
      { 
       Possible[7] = 0; 
       Have = Word.substr(0, 1); 

       return Find(Word, Backup, Backup1, 1, Have, Matrix, Possible, Backup, Backup1); 
      } 
     } 

     return false; 
    } 

    string Diro(int * Possible) 
    { 
     string Dir; 

     bool Next = true; 

     if(Possible[0] == 1 && Next == true) 
     { 
      Dir = " From right to left"; 
      Next = false; 
     } 

     if(Possible[1] == 1 && Next == true) 
     { 
      Dir = " From left to right"; 
      Next = false; 
     } 

     if(Possible[2] == 1 && Next == true) 
     { 
      Dir = " From top to bottom"; 
      Next = false; 
     } 

     if(Possible[3] == 1 && Next == true) 
     { 
      Dir = " From bottom to top"; 
      Next = false; 
     } 

     if(Possible[4] == 1 && Next == true) 
     { 
      Dir = " "; 
      Next = false; 
     } 

     if(Possible[5] == 1 && Next == true) 
     { 
      Dir = " "; 
      Next = false; 
     } 

     if(Possible[6] == 1 && Next == true) 
     { 
      Dir = " "; 
      Next = false; 
     } 

     if(Possible[7] == 1 && Next == true) 
     { 
      Dir = " "; 
      Next = false; 
     } 

     return Dir; 
    } 

    int main() 
    { 
     int Height = 0, Widht = 0, Numb = 0; 

     int Loop[] = {0, 0, 0, 0, 0, 0, 0, 0, 0}; 

     int * Possible = new int[8]; 

     string Dir, Search, Tempo, Temp; 

     ifstream Data("C:/Users/Magician/AppData/Local/VirtualStore/Program Files (x86)/CodeBlocks/MakeMaze/Files/Maze.txt"); 

     Data >> Widht >> Height; 

     string * NewMatrix = new string[Height]; 

     while(Loop[7] < Height) 
     { 
      Tempo = ""; 
      Loop[8] = 0; 

      while(Loop[8] < Widht) 
      { 
       Data >> Temp; 
       Tempo += Temp; 
       Loop[8]++; 
      } 

      NewMatrix[Loop[7]] = Tempo; 

      Loop[7]++; 
     } 

     Data >> Numb; 

     string * Words = new string[Numb]; 

     while(Loop[2] < Numb) 
     { 
      Data >> Words[Loop[2]]; 

      Loop[2]++; 
     } 

     Data.close(); 

     while(Loop[3] < Numb) 
     { 
      Search = Words[Loop[3]].substr(0, 1); 
      Loop[4] = 0; 

      while(Loop[4] < Height) 
      { 
       Loop[5] = 0; 

       while(Loop[5] < Widht) 
       { 
        if(NewMatrix[Loop[4]].substr(Loop[5], 1) == Search) 
        { 
         Zero(Possible); 
         Possibles(Widht, Height, Loop[4], Loop[5], Words[Loop[3]].size(), Possible); 

         if(Find(Words[Loop[3]], Loop[4], Loop[5], 1, Search, NewMatrix, Possible, Loop[4], Loop[5])) 
         { 
          cout << Words[Loop[3]] << " At: " << Loop[4] + 1 << " collumn, symbol " << Loop[5] + 1 << " " << Diro(Possible) << endl; 

          Loop[5] = Widht; 
          Loop[4] = Height; 
         } 
        } 

        Loop[5]++; 
       } 

       Loop[4]++; 
      } 

      Loop[3]++; 
     } 

     delete [] Possible; 
     delete [] Words; 
     delete [] NewMatrix; 

     return 0; 
    } 

Если вы не поняли, что я написал раньше: когда я комментирую каждый если (возможно [] ==) за исключением случаев, когда (возможно [5] == 1) в функции Find() работает алгоритм, но все это разрешено. Я пробовал с матрицей 100 * 100 с множеством слов, чтобы найти, и все в порядке.

Answer 1

1. Одно условия в Possibles неправильно:

   /* INCORRECT: Should be [ Poz >= Leng - 1 ] */ 
   if(Poz >= Leng) // From bottom to top 
   { 
       Possible[3] = 1; 
   } 
   

   Но это одна только логическая ошибка и не должен вызывать ошибки сегментации.

2. Похоже, вы столкнулись с переполнением стека.

   сделаем простой расчет. Для 10000 * 10000 матрицы и длины слова 10000, если вы начнете звонить Find() в левом верхнем углу матрицы, то возможны три направления. В худшем случае, Find() будет проходить около 10000 * 3 элементов. Примечание в Func() есть 3 строковых экземпляра (sizeof (string) == 24 в 32bit VC2013), плюс различные целые числа. Размер одного кадра может легко превышать 100 байт. Поскольку вы используете рекурсивные вызовы, это может привести к использованию стека не менее 10000 * 3 * 100 = 3000000 байт = прибл. 3M.

   Это число не очень большое, но достаточно для переполнения стека, так как Windows имеет размер стека по умолчанию 1M. (http://msdn.microsoft.com/en-us/library/8cxs58a6.aspx)

Рекомендация для улучшения

Это мой шаблон используется, чтобы решить эти виды matrix traversal проблем.

Во-первых, определить постоянный массив для хранения смещения для движений (Moore neighborhood):

const int delta[8][2] = { 
    { 1, 0 }, { 1, 1 }, { 0, 1 }, { -1, 1 }, 
    { -1, 0 }, { -1, -1 }, { 0, -1 }, { 1, -1 } 
}; 

Во-вторых, использование одного for для проверки всех направлений:

int initial_x = .., initial_y = ..; 
for (int dir = 0; dir < 8; dir++) { 
    for (int count = 0; count < WORD_LENGTH; count++) { 
     int current_x = initial_x + delta[dir][0] * count; 
     int current_y = initial_y + delta[dir][1] * count; 
     if (IS_INVALID(current_x, current_y)) { 
      break; 
     } 
    } 
} 

Последний, вставить различные код и флаги для завершения программы.

Другая подсказка: вы можете использовать char тип получить и сравнить один символ в строке (Использовать word[idx] получить idx-й символ word). Это может быть значительно быстрее, чем при использовании substr.