// о чем можно написать:
// - оценка сложности алгоритмов и почему важно делать быстрые алгоритмы
// 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/
// - что такое наивный алгоритм (примитивный, поиск "в лоб")
// - как работает каждый из реализованных в этой проге алгоритмов
// (схемы, картинки или видео)
// - сравнение оценки сложности этих алгоритмов
#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;
}