Реализовать алгоритмы поиска подстроки в строке. - 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;
}

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

  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
Похожие ответы