Реализовать алгоритмы поиска подстроки в строке. - C (СИ)
Формулировка задачи:
Здравствуйте,требуется на основе алгоритмов прямого поиска; Кнута, Морриса и Пратта; Боуера и Мура
реализовать алгоритмы поиска подстроки в строке.
Самый простой способ.
Спасибо
Решение задачи: «Реализовать алгоритмы поиска подстроки в строке.»
textual
Листинг программы
int strstr(const char *text, const char *pattern) { // Если шаблон подстроки пустой, то возвращаем 0 if (! *pattern) return 0; // Необходимые переменные. int pos = -1; const char *a, * b; b = pattern; // перебираем строку посимвольно. Как мы помним C-строка - это массив символов. Поэтому нам удобнее работать через указатели. for (; *text != 0; text++){ // увеличиваем значение позиции на 1. pos++; // В случае, если исмволы не идентичны, остальной код пропускаем. if (*text != *b) { continue; } // Если че у нас символ в текущей позиции строки равен первому символу шаблона, то запускаем бесконечный цикл. // Он прерывается в случае несовпадения символов. // "а" присваиваем "text" с ее текущей позиции. Тогда позиция text в цикле не меняется, а меняется позиция в "a". a = text; while(1) { // Если b достиг конца шаблона, то мы нашли полное совпадение и можем вернуть позицию pos if (*b == 0){ return pos; } // Если же следующие символы не равны, то прерываем функцию if (*a++ != *b++) { break; } } // Позицию в b снова сбрасываем на начало. b = pattern; } return -1; }
Объяснение кода листинга программы
- Функция
strstr
принимает два аргумента:text
- строка, в которой ищется подстрока, иpattern
- сама подстрока. - Если подстрока пустая, функция возвращает 0.
- В первой итерации цикла функция проверяет, равен ли первый символ строки
text
первому символу подстрокиpattern
. Если да, то начинается поиск совпадения. - Если символы не совпадают, функция пропускает текущую итерацию и переходит к следующей.
- Если подстрока закончилась (т.е.
*pattern
равен 0), функция возвращает позицию, на которой найдено совпадение. - Если текущий символ строки
text
не равен следующему символу подстрокиpattern
, функция прерывает поиск и возвращает -1. - Если текущий символ строки
text
равен следующему символу подстрокиpattern
, функция продолжает поиск с следующей позиции. - Если подстрока не найдена, функция возвращает -1.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д