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




алгоритмы поиска с++, поиск подстроки в строке, 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 достаточно удобный для работы со строками именно, как строками, а не просто с массивом символов.

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

Дата
Страница
Поиск подстроки в строке С++
Рейтинг
51star1star1star1star1star

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

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

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

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

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

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

Код размещайте в тегах: <pre class="lang:c++ decode:true ">YOUR CODE</pre>