Substring search (BM, KMP)

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396

// о чем можно написать:

// - оценка сложности алгоритмов и почему важно делать быстрые алгоритмы

// 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;

}

// о чем можно написать:
// - оценка сложности алгоритмов и почему важно делать быстрые алгоритмы
//   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;
}

INFO

Quick actions

Substring search (BM, KMP)

Snippet info