void bmSearch(string str, string substr, bool reg) {
  int iterations = 0;
  bool flag = false;
  //Вычислить длину исходной строки
  int n = str.length();

  //Вычислить длину образа
  int m = substr.length();

  //Заполнить таблицу для этого алгоритма
  vector < int > d;
  d.reserve(ALPHABET_LENGTH);
  d = bmTable(substr, reg);

  //Переменная смещения образа по отношению к тексту
  int s = 0;
  if (reg) {
    //Пока s меньше, чем разность длины строки и образа
    while (s <= (n - m)) {
      int j = m - 1;

      //Если образ совпадает со строкой, начиная с конца
      if ((j >= 0) && compareWithRegister(substr[j], str[s + j]))
        while ((j >= 0) && compareWithRegister(substr[j], str[s + j])) {
          j--; //Двигаться от конца образа
          iterations++;
        }
      else {
        iterations++;
      }

      //Если образ полностью совпал со строкой
      if (j < 0) {
        cout << "found " << s << endl;
        flag = true;

        //Сдвинуть образ так, чтобы следующий символ в тексте совпадал с последним
        //таким же символом в образе или на 1, если длины строки не хватает
        if (reg)
          s += ((s + m) < n) ? m - d[str[s + m]] : 1;
        else
          s += ((s + m) < n) ? m - d[tolower(str[s + m])] : 1;
      } else {
        //Сдвинуть образ так, чтобы символ в тексте, не совпавший с символом
        //в образе, совпадал с последним таким же символом в образе или на 1,
        //если совпадающий символ правее текущего символа в образе
        if (reg) {
          if (1 >= (j - d[str[s + j]])) {
            s++;
          } else {
            s += j - d[str[s + j]];
          }

        } else{
            if (1 >= (j - d[tolower(str[s + j]]))) {
            s++;
          } else {
            s += j - d[tolower(str[s + j])];
          }
        }
      }
    }
  } else {
    while (s <= (n - m)) {
      int j = m - 1;

      //Если образ совпадает со строкой, начиная с конца
      if ((j >= 0) && compareWithRegister(substr[j], str[s + j]))
        while ((j >= 0) && compareWithoutRegister(substr[j], str[s + j])) {
          j--; //Двигаться от конца образа
          iterations++;
        }
      else {
        iterations++;
      }

      //Если образ полностью совпал со строкой
      if (j < 0) {
        cout << "Found with BM, index " << s << endl;
        flag = true;

        //Сдвинуть образ так, чтобы следующий символ в тексте совпадал с последним
        //таким же символом в образе или на 1, если длины строки не хватает
        if (reg){
            if (((s + m) < n)) {
            s+= m - d[str[s + m]];
          } else {
            s++;
          }
            }
        else{
            if (((s + m) < n)) {
            s+= m - d[tolower(str[s + m])];
          } else {
            s++;
        }
      } else {
        //Сдвинуть образ так, чтобы символ в тексте, не совпавший с символом
        //в образе, совпадал с последним таким же символом в образе или на 1,
        //если совпадающий символ правее текущего символа в образе
        if (reg) {
          if (1 >= (j - d[str[s + j]])) {
            s++;
          } else {
            s += j - d[str[s + j]];
          }

        } else{
            if (1 >= (j - d[str[s + j]])) {
            s++;
          } else {
            s += j - d[tolower(str[s + j])];
          }
        }
      }
    }
  }
  // flag нужен, чтобы нот фаунд не выводилось после успешного нахождения
  if ((s > n - m) & !(flag))
    cout << "Not found with BM" << endl;
  cout << "BM iterations = " << iterations << endl;
}