Substring search (BM, KMP)

// о чем можно написать:
// - оценка сложности алгоритмов и почему важно делать быстрые алгоритмы
//   https://tproger.ru/translations/algorithms-and-data-structures/
// - зачем вообще нужно создавать быстрые алгоритмы
// - сравнение поисковых алгоритмов
//   https://en.wikipedia.org/wiki/String_searching_algorithm
//   https://ru.wikipedia.org/wiki/Поиск_подстроки
//   https://habrahabr.ru/post/111449/
// - что такое наивный алгоритм (примитивный, поиск "в лоб")
// - как работает каждый из реализованных в этой проге алгоритмов
//   (схемы, картинки или видео)
// - сравнение оценки сложности этих алгоритмов

// анимация алгоритмов поиска
// http://whocouldthat.be/visualizing-string-matching/

#include <stdio.h>  // printf
#include <string.h> // strlen
#include <limits.h> // константа CHAR_MAX

// что такое индекс вхождения:
// индекс вхождения подстроки "ложк" в строку "ложка" равен 0 (после 0 символов)
// индекс вхождения подстроки "жка" в строку "ложка" равен 2 (после 2 символов)
// индекс вхождения подстроки "а" в строку "ложка" равен 4 (после 4 символов)
// индекс вхождения подстроки "крякрякря" в строку "ложка" равен -1 (не найдена)

/*
  обозначения в этом коде:
  haystack (стог сена) - строка
  needle (иголка) - подстрока
  hlen - длина строки
  nlen - длина подстроки
  (от англ. search needle in haystack problem)
  (в некоторых статьях обозначают по другому, читаем внимательно)
*/

// структура совпадения
struct Match {
  int index;      // индекс вхождения подстроки в строку
  char* haystack; // указатель на строку, в которой производился поиск
  char* needle;   // указатель на искомою подстроку
  int steps;      // число пройденных шагов
};

typedef struct Match Match; // чтобы писать Match вместо struct Match

// прописываем прототипы функций вначале, чтобы не было проблемы, когда одна
// функция ссылается на другую, которая написана после первой
int min(int a, int b);
int max(int a, int b);
void print_match(Match match);
void generate_prefix(int* prefix_table, char* needle);
Match search_naive(char* haystack, char* needle);
Match search_kmp(char* haystack, char* needle);
Match search_bm(char* haystack, char* needle);

/*
  возвращает мин. число из двух
*/
int min(int a, int b) {
  if (a < b) {
    return a;
  } else {
    return b;
  }
}

/*
  возвращает макс. число из двух
*/
int max(int a, int b) {
  if (a > b) {
    return a;
  } else {
    return b;
  }
}

/*
  печатает информацию о совпадении

  кстати, match хранит лишь указатели (ссылки) на подстроку и строку.
  сами строки в match не хранятся.
  это значит, при их изменении или удалении вне этой функции, выведенная на
  экран информация будет неактуальна.
*/
void match_print(Match match) {
  // используем \" \" чтобы напечатать кавычки с помощью printf
  printf("\"%s\" ", match.needle);

  if (match.index == -1) {
    printf("not found");
  } else {
    printf("found at position %i", match.index);
  }

  printf(" after %i steps in \"%s\"\n",  match.steps, match.haystack);
}

/*
  простой поиск "в лоб". натыкаемся на первое совпадение, и начинаем сравнивать
  символы. если не совпало, отменяем сравнение, и сдвигаеся на 1 символ дальше.

  в общем об алгоритме
  https://www.youtube.com/watch?v=KUbsdGm3G7s

  данный код оптимизирован под особенности языка си
*/
Match search_naive(char* haystack, char* needle) {
  // структура совпадения
  Match match = {
    .index = -1,  // подстрока еще не найдена, индекс её вхождения в строку = -1
    .haystack = haystack, // запоминаем указатель на строку, в которой был поиск
    .needle = needle,
    .steps = 0
  };

  int i, j;

  int nlen = strlen(needle);

  // проходимся по строке.
  // обходимся без предварительного вычисления длины всей строки.
  // цикл продолжается, пока текущий символ не будет null-terminator'ом.
  // последние nlen - 1 символов мы пропускаем, ибо там уже понятно, что
  // место для поиска в строке кончилось
  // подробнее тут: https://glot.io/snippets/epaq5yxcf0
  for (i = 0; haystack[i + nlen - 1] != '\0'; i++) {
    // проходимся по подстроке
    // в шапке этого цикла нет условия продолжения
    // мы будем это контроллировать с помощью пары if-ов
    for (j = 0; ; j++) {
      match.steps++;
      if (needle[j] == '\0') {
        // если мы дошли до null-terminator в конце подстроки,
        // и до сих пор все символы совпадали, значит подстрока нашлась.
        match.index = i;  // записываем с какой позиции она находится в строке

        // возвращаем совпадение
        return match;
      }
      if (haystack[i + j] != needle[j]) {
        // считаем шаги
        // если текущий символ подстроки и текущий символ строки не совпали,
        // то принудительно останавливаем этот подцикл, и переходим к следующей
        // итерации i во внешнем цикле
        break;
      }
    }
  }

  // если подстрока не нашлесь. то после завершения цикла просто возвращаем
  // совпадение с теми параметрами, которые были заданы в самом начале
  return match;
}

/*
  заполняет данную таблицу совпадения префиксов с суффиксами
  используется в обоих kmp и bm

  аргументы функции:
  - указатель на таблицу
  - указатель подстроку
*/

void generate_prefix(int* prefix_table, char* needle) {
  prefix_table[0] = 0;

  int i = 1, j = 0;

  while (needle[i] != '\0') {
    while (j > 0 && needle[i] != needle[j]) {
      // пока j не вернулся в начало строки И пока проверяемые i-тый
      // и j-тый символы не равны, перемещаем j на ранее расчитанную позицию из
      // таблицы, и проверяем снова. цикл закончится, как только дойдем до
      // начала подстроки или как только наткнемся на одинаковые символы
      j = prefix_table[j - 1];
    }

    if (needle[i] == needle[j]) {
      // попались одинаковые символы? увеличиваем j, будем проверять следующий
      // символ
      j++;
    }

    // записываем текущее значение j в таблицу. если 3 раза попутся одинаковые
    // пары букв, то j будет равен 3. если 0, то 0.
    prefix_table[i] = j;

    i++;
  }
}

/*
  алгоритм Кнута Морриса и Пратта.

  более "умный" вариант поиска, умеет пропускать ненужные проверки совпадений,
  используя специальную таблицу префиксов, что существенно ускоряет процесс.

  как работает алгоритм и таблица префиксов (наглядно)
  https://www.youtube.com/watch?v=v82y5TCcBhQ

  как строится таблица префиксов (наглядно)
  https://youtu.be/GTJr8OvyEVQ?t=5m44s

  пара статей
  https://habrahabr.ru/post/307220/
  https://habrahabr.ru/post/113266/
*/
Match search_kmp(char* haystack, char* needle) {
  Match match = {
    .index = -1,
    .haystack = haystack,
    .needle = needle,
    .steps = 0
  };

  // вычисляем длину подстроки
  int nlen = strlen(needle);

  // создаем таблицу префиксов нужного размера для подстрокиs
  int prefix[nlen];

  // ТАБЛИЦА ПРЕФИКСОВ
  generate_prefix(prefix, needle);

  int i, j;

  // ПОИСК
  for (i = 0, j = 0; haystack[i] != '\0'; i++) {
    while (j > 0 && haystack[i] != needle[j]) {
      match.steps++;
      // когда мы не находимся в начале строки,
      // если символы не совпадают, перемещаем j на ту позицию, что
      // указана в пред. ячейке таблице префиксов
      // и так пока не дойдем до начала строки или не найдем одинаковые символы
      j = prefix[j - 1];
    }
    if (haystack[i] == needle[j]) {
      match.steps++;
      // если нашли одинаковые символы, передвигаем j вперед на 1
      j++;
    }
    if (needle[j] == '\0') {
      // если мы дошли до null-terminator'а подстроки и все символы совпали,
      // значит подстрока найдена
      match.index = i - j + 1;  // i сейчас сдвинут вправо на (j - 1)
                                // чтобы правильно записать позицию,
                                // вычитаем этот сдвиг
      return match;
    }
  }

  // если подстрока не нашлась, возвращаем match без изменений
  return match;
}

/*
  генерирует таблицу суффиксов
  алгоритм взят с вики. основан на тех же идеях, что и алгоритмы вычисления
  префикс-функции и Z-функции строки.
*/

void generate_suffix(int* suffix_table, char* needle, int nlen) {
  int i, j;

  int z_table[nlen];

  for (i = 0; i < nlen; i++) {
    z_table[i] = 0;
    suffix_table[i] = nlen;
  }
  suffix_table[nlen] = nlen;

  int max_z_id_x = 0, max_z = 0;

  for (i = 1; i < nlen; i++) {
    if (i < max_z) {
      z_table[i] = min(max_z - i + 1, z_table[i - max_z]);
    }
    while (i + z_table[i] < nlen && needle[nlen - 1 - z_table[i]] == needle[nlen - 1 - (i + z_table[i])]) {
      z_table[i]++;
    }
    if (i + z_table[i] - 1 > max_z) {
      max_z_id_x = i;
      max_z = i + z_table[i] - 1;
    }
  }

  for (i = nlen - 1; i > 0; i--) {
    suffix_table[nlen - z_table[i]] = i;
  }

  for (i = 1, j = 0; i <= nlen - 1; i++) {
    if (i + z_table[i] == nlen) {
      for (; j <= i; j++) {
        if (suffix_table[j] == nlen) {
          suffix_table[j] = i;
        }
      }
    }
  }
}

/*
  алгоритм Бойера-Мура

  проверяет слова с конца
  строит две таблицы для пропусков по разным правилам:
  bad character rule
  good suffix rule
  этот алгоритм поиска чаще всего используется в программах

  wiki
  https://ru.wikipedia.org/wiki/Алгоритм_Бойера_—_Мура

  хорошее объяснение, как работает алгоритм
  https://www.youtube.com/watch?v=4Xyhb72LCX4
  https://www.youtube.com/watch?v=Wj606N0IAsw


*/
Match search_bm(char* haystack, char* needle) {
  Match match = {
    .index = -1,
    .haystack = haystack,
    .needle = needle,
    .steps = 0
  };

  int i, j;

  int nlen = strlen(needle);

  // ТАБЛИЦА СТОП СИМВОЛОВ
  int stop_table[CHAR_MAX + 1];
  // заполняем таблицу -1
  for (i = 0; i < CHAR_MAX + 1; i++) {
    stop_table[i] = -1;
  }
  // записываем в таблицу последнее вхождение каждого символа подстроки
  for (i = 0; i < nlen - 1; i++) {
    stop_table[needle[i]] = i;
  }

  // ТАБЛИЦА СУФФИКСОВ
  int suffix_table[nlen + 1];
  generate_suffix(suffix_table, needle, nlen);

  // ПОИСК
  for (i = 0; haystack[i + nlen - 1] != '\0'; i++) {
    // сверка начнется с конца
    j = nlen - 1;
    // сверяем символы
    while (haystack[i + j] == needle[j]) {
      match.steps++;
      if (j == 0) {
        // если дошли до начала подстроки и небыло несовпадений,
        // то подстрока найдена
        match.index = i + j;
        return match;
      }

      j--;
    }

    // если не совпало, пропускаем как можно больше символов,
    // основываясь на данных из таблицы суффиксов и таблицы стоп-слов
    j += max(suffix_table[j], j - stop_table[haystack[i + j]]);
    //            ^                   ^
    //         суффикс            стоп-символ
  }

  return match;
}

int main() {
  char* haystack = "ABC ABCDAB ABCDABCDABDE";

  char* needle = "ABCDABD";

  printf("Naive search:\n");
  Match match_naive = search_naive(haystack, needle);
  match_print(match_naive);

  printf("\nKMP search:\n");
  Match match_kmp = search_kmp(haystack, needle);
  match_print(match_kmp);

  printf("\nBM search:\n");
  Match match_bm = search_bm(haystack, needle);
  match_print(match_bm);

  return 0;
}