20. Поиск подстроки [решение]

Run Settings
LanguageC
Language Version
Run Command
// о чем можно написать: // - оценка сложности алгоритмов и почему важно делать быстрые алгоритмы // 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; }
Editor Settings
Theme
Key bindings
Full width
Lines