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