Поиск подстроки в строке




алгоритмы поиска с++, поиск подстроки в строке, c++, как найти подстроку в строкеСейчас мы разберём на примерах, как может выглядеть алгоритм поиска подстроки в строке. Примеры будут основываться на функциях стандартных библиотек, ведь именно в таких функциях и проявляются все удобства написания программ. А вот классический разбор алгоритма, основанный на циклах и сравнениях, также достаточно примечателен. Поэтому мы его рассмотрим в этом же уроке.

Сам алгоритм в принципе очень прост. Есть две строки. Например "Hello world" и "lo"

Работать будем в два цикла:

  1. Первый будет выполнять проход по всей строке, и искать местоположение первой буквы искомой строки ( "lo" ).
  2. Второй, начиная с найденной позиции первой буквы – сверять, какие буквы стоят после неё и сколько из них подряд совпадают.

Проиллюстрируем поиск подстроки в строке:

алгоритмы поиска с++, поиск подстроки в строке, c++, как найти подстроку в строке, программирование на с++ для начинающих, доклад, курсовая работа

На первых двух итерациях цикла сравниваемые буквы не будут совпадать (выделено красным). На третьей итерации искомая буква (первый символ искомого слова) совпала с символом в строке, где происходит поиск. При таком совпадении в работу включается второй цикл. Он призван отсчитывать количество символов после первого в искомой строке, которые будут совпадать с символами в строке исходной. Если один из следующих символов не совпадает – цикл завершает свою работу. Нет смысла гонять цикл впустую, после первого несовпадения, так как уже понятно, что искомого тут нет.

На третьей итерации совпал только первый символ искомой строки, а вот второй уже не совпадает. Придется первому циклу продолжить работу. Четвертая итерация дает необходимые результаты – совпадают все символы искомой строки с частью исходной строки. А раз все символы совпали – подстрока найдена. Работу алгоритма можно закончить.

Посмотрим, как выглядит классический код поиска подстроки в строке в С++:

Два цикла выполняют каждый свою задачу. Один топает по строке в надежде найти “голову” искомого слова (первый символ). Второй выясняет, есть ли после найденной “головы” “тело” искомого. Причем проверяет, не лежит ли это “тело” в конце строки. Т.е. не является ли длина найденного слова на единицу больше длины искомой строки, если учитывать, что в эту единицу попадает нулль-терминатор ( '\0' ).

алгоритмы поиска с++, поиск подстроки в строке, c++, как найти подстроку в строке, программирование на с++ для начинающих, доклад, курсовая работа

Мы видим, что программа нашла начало подстроки pa в ячейках символьного массива с индексом 0 и 4. Но почему? Ведь в слове parapapa 3 таких подстроки. Все дело в '\0' .

В целом смысл самого алгоритма на этом заканчивается. Больше никаких сложностей кроме нуля в конце строки нет. Однако, следует обратить внимание на множественность поиска. Что, если нам необходимо найти в строке несколько позиций? Сколько раз искомое слово встречается в строке и в каких местах? Именно это и призван контролировать третий параметр – int nномер вхождения в строку. Если поставить туда единицу – он найдет первое совпадение искомого. Если двойку, он заставит первый цикл пропустить найденное первое, и искать второе. Если тройку – искать третье и так далее. С каждым найденным искомым словом, этот счетчик вхождений уменьшается на единицу. Это и позволяет описать поиск в цикле:

То есть найти первое, второе, третье, четвертое совпадение… Пока функция не вернет -1, что укажет на отсутствие N-ного искомого в строке.

 

Теперь, для сравнения, поиск подстроки в строке С++ с хедером string.

Все! Класс string в С++ снабжен методом find(), возвращающий номер ячейки, с которого начинается тело искомой строки в исходной строке. Результат:

алгоритмы поиска с++, поиск подстроки в строке, c++, как найти подстроку в строке, программирование на с++ для начинающих, доклад, курсовая работа

Как же множественность? Да пожалуйста:

Функция find() принимает вторым параметром номер символа, с которого начать поиск. Т.е. найдя первое вхождение, его значение увеличивается на единицу и find() продолжает поиск со следующего символа после найденной головы. Результат:

алгоритмы поиска с++, поиск подстроки в строке, c++, как найти подстроку в строке, программирование на с++ для начинающих, доклад, курсовая работа

Всё это есть в С++, и сам класс string достаточно удобный для работы со строками именно, как строками, а не просто с массивом символов.

Рассылка новых уроков по программированию:

Поиск подстроки в строке
5 (100%) 4 votes

Поиск подстроки в строке: 7 комментариев

  1. мне кажется так лучше, так как избавляемся проверки на ноль символ

    1. Вообще то, в языке C, и унаследовано в C++, считается, что числовое значение 0 соответствует false (нарушению условия), а любое ненулевое значение – true (соблюдению условия).
      Поэтому формально if( n – 1 ) равнозначно if( n != 1 ).

      P.S. Формально потому, что в корректность кода вообще я не вникал.

    2. К такой записи следует привыкнуть, потому что в реальном коде на C/C++ такая запись встречается достаточно часто, особенно при сравнении указателей с значением NULL:

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *