Реализовать алгоритмы поиска подстроки в строке. - C (СИ)

Узнай цену своей работы

Формулировка задачи:

Здравствуйте,требуется на основе алгоритмов прямого поиска; Кнута, Морриса и Пратта; Боуера и Мура реализовать алгоритмы поиска подстроки в строке. Самый простой способ. Спасибо

Решение задачи: «Реализовать алгоритмы поиска подстроки в строке.»

textual
Листинг программы
  1. int strstr(const char *text, const char *pattern)
  2. {
  3.     //  Если шаблон подстроки пустой, то возвращаем 0
  4.     if (! *pattern)
  5.         return 0;
  6.  
  7.     // Необходимые переменные.
  8.     int pos = -1;
  9.     const char *a, * b;
  10.  
  11.     b = pattern;
  12.  
  13.     // перебираем строку посимвольно. Как мы помним C-строка - это массив символов. Поэтому нам удобнее работать через указатели.
  14.     for (; *text != 0; text++){
  15.         // увеличиваем значение позиции на 1.
  16.         pos++;
  17.  
  18.         // В случае, если исмволы не идентичны, остальной код пропускаем.
  19.         if (*text != *b) {
  20.             continue;
  21.         }
  22.  
  23.         // Если че у нас символ в текущей позиции строки равен первому символу шаблона, то запускаем бесконечный цикл.
  24.         // Он прерывается в случае несовпадения символов.
  25.  
  26.         // "а" присваиваем "text" с ее текущей позиции. Тогда позиция text в цикле не меняется, а меняется позиция в "a".
  27.         a = text;
  28.  
  29.         while(1) {
  30.  
  31.             // Если b достиг конца шаблона, то мы нашли полное совпадение и можем вернуть позицию pos
  32.             if (*b == 0){
  33.                 return pos;
  34.             }
  35.  
  36.             // Если же следующие символы не равны, то прерываем функцию
  37.             if (*a++ != *b++) {
  38.                 break;
  39.             }
  40.         }
  41.  
  42.         // Позицию в b снова сбрасываем на начало.
  43.         b = pattern;
  44.     }
  45.  
  46.     return -1;
  47. }

Объяснение кода листинга программы

  1. Функция strstr принимает два аргумента: text - строка, в которой ищется подстрока, и pattern - сама подстрока.
  2. Если подстрока пустая, функция возвращает 0.
  3. В первой итерации цикла функция проверяет, равен ли первый символ строки text первому символу подстроки pattern. Если да, то начинается поиск совпадения.
  4. Если символы не совпадают, функция пропускает текущую итерацию и переходит к следующей.
  5. Если подстрока закончилась (т.е. *pattern равен 0), функция возвращает позицию, на которой найдено совпадение.
  6. Если текущий символ строки text не равен следующему символу подстроки pattern, функция прерывает поиск и возвращает -1.
  7. Если текущий символ строки text равен следующему символу подстроки pattern, функция продолжает поиск с следующей позиции.
  8. Если подстрока не найдена, функция возвращает -1.

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

10   голосов , оценка 3.9 из 5

Нужна аналогичная работа?

Оформи быстрый заказ и узнай стоимость

Бесплатно
Оформите заказ и авторы начнут откликаться уже через 10 минут
Похожие ответы