Реализовать алгоритмы поиска подстроки в строке. - 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.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д