Прокомментировать код (Алгоритм Бойера — Мура)

[EDWIN503]

Добрый день, искал различные методы поиска подстроки в строке и наткнулся на Алгоритм Бойера — Мура, в принципе работа алгоритма понятна, начал искать реализацию и вот что нашел:

#include <stdio.h>
#include <stdlib.h>
#include <locale.h>

int BMSearch(char *string, char *substring){
  int  sl = 0;
  int ssl = 0;
  int res = -1;
  while (string[sl] != NULL) {
  		sl++;
  }
  while (substring[ssl] != NULL) {
  		ssl++;
  }
  if (sl == 0) 
    printf("Некорректная строка\n"); 
  else if (ssl == 0) 
    printf("Некорректная подстрока\n"); 
  else {
    int  i, Pos;
    int  BMT[256];
    for (i = 0; i < 256; i ++)
      BMT[i] = ssl;
    for (i = ssl-1; i >= 0; i--)
      if (BMT[(short)(substring[i])] == ssl) 
        BMT[(short)(substring[i])] = ssl - i - 1;
    Pos = ssl - 1;
    while (Pos < sl)
      if (substring[ssl - 1] != string[Pos])
        Pos = Pos + BMT[(short)(string[Pos])];
      else 
        for (i = ssl - 2; i >= 0; i--){
          if (substring[i] != string[Pos - ssl + i + 1]) {
            Pos += BMT[(short)(string[Pos - ssl + i + 1])] - 1;
            break;
          }
          else
            if (i == 0)
              return Pos - ssl + 1;
        }
  }
  printf("\n");
  return res;
}

int main(int argc, char *argv[]) {
	setlocale (LC_ALL, "Rus");
	char str[30];
	char substr[30];
	printf("Введите строку: ");
	scanf("%s", str);
	printf("Введите подстроку: ");
	scanf("%s", substr);
	
	int pos = BMSearch(str, substr);
	printf("Смещение = %d", pos);
		
	return 0;
}

Не могли бы вы описать мне, что происходит в данном куске кода:

    int  i, Pos;
    int  BMT[256];
    for (i = 0; i < 256; i ++)
      BMT[i] = ssl;
    for (i = ssl-1; i >= 0; i--)
      if (BMT[(short)(substring[i])] == ssl) 
        BMT[(short)(substring[i])] = ssl - i - 1;
    Pos = ssl - 1;
    while (Pos < sl)
      if (substring[ssl - 1] != string[Pos])
        Pos = Pos + BMT[(short)(string[Pos])];
      else 
        for (i = ssl - 2; i >= 0; i--){
          if (substring[i] != string[Pos - ssl + i + 1]) {
            Pos += BMT[(short)(string[Pos - ssl + i + 1])] - 1;
            break;
          }
          else
            if (i == 0)
              return Pos - ssl + 1;
        }

Заранее спасибо, очень благодарен вам

[ura_111]

Если ты хочешь разобраться как работает код, то тебе надо просто по-шагово его выполнить (на конкретном примере выполнить).
Т.е. прими какие-то условия, например:

string = "sdgshju dgjdfg fvbsfjh dfdsgjgdn dgh"
substring = "fdsg"

и, у себя на бумажке, пройди код.
При этом записывай как меняются переменные и их анализируй...
Если с первого раза не получилось - пройди повторно... Со временем понимание придёт...

Ты же знаешь, что в С++ строка сохраняется как обычный массив типа "char"?

[EDWIN503]

Сообщение от ura_111

Если ты хочешь разобраться как работает код, то тебе надо просто по-шагово его выполнить (на конкретном примере выполнить).
Т.е. прими какие-то условия, например:

string = "sdgshju dgjdfg fvbsfjh dfdsgjgdn dgh"
substring = "fdsg"

и, у себя на бумажке, пройди код.
При этом записывай как меняются переменные и их анализируй...
Если с первого раза не получилось - пройди повторно... Со временем понимание придёт...

Ты же знаешь, что в С++ строка сохраняется как обычный массив типа "char"?

Я не понимаю эту часть кода, не могли бы вы подсказать мне?

if (BMT[(short)(substring[i])] == ssl)

Конкретно интересует часть в квадратных скобках:

[(short)(substring[i])]

Подскажите, что делает этот код?

[ura_111]

Посмотри на описание массива: "BMT[256];"... Чтобы обратится к "115-му" элементу нужно написать "BMT[115]", где "115" - это целое число (а не символ 's')...

А теперь теория: в с++ между символом "char" и "int" есть связь. Или, по другому, один и тот же символ можно приставить и как целое число и как символ. Это называется таблица ASCII:


1.jpg


Обычно я использовал это свойство, когда нужно подсчитать кол-во каждого символа в строке : "tdgfr tt rr t". Создаёшь массив "int" из 256 символов (Подумай, а почему именно из 256 символов?) и каждой ячейки сохраняешь сумму. Например A[115] - это для хранения кол-ва встречения буквы 's', а A[111] - счётчик для 'o' и т.д.

Возьми поиграйся с выводом разных значений: и таких (short)(substring[i]) - кстате, какой у этого выражения тип на выходе (для вывода нужно указать)?
(ну раз массив int BMT[int]???)
и другого вида...

https://www.youtube.com/watch?v=4XX-...ature=youtu.be

[ura_111]

Не дописал таблицу:

2.jpg


Подумай, почему именно вектор из 256 элементов?

[ura_111]

Еще один вопрос: эквиваленты ли записи

int a=1;
char b= '1';

а так:

int a=49;
char b= '1';

????

[ura_111]

Понимаешь, в Си есть такая тема как "приведение типов" - это когда из одного типа делается другой (если это возможно).
Например, из "doube" в "int" или вот пример:



2.jpg


После приведения, выполняются арифметические действия (хотя изначально С- это char)...

Наверное, в строчке "[(short)(substring[i])]" надо поменять "short" на "int" и тогда будет нормально смотреться, - ведь "BMT[int]".

А ну пробуй, заработает программа?

[EDWIN503]

Да, заработала, в принципе, если не ставить ничего, ни short, ни int, то тоже работает

[ura_111]

может быть "явное" и "не явное" преобразование типов. В последнем случае компилятор сам решает стоить это делать или нет (от контекста).



3.jpg

[ura_111]

Но с этим нужно быть осторожным...
За типами нужно следить, потому что появляются ошибки: например ты присвоил:

bouble a=6.88;
int b= a;

всё... после запятой всё пропало.

Понимаешь?