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

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

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

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

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

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

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

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

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

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

#include <iostream>

// Функция для поиска подстроки в строке
// + поиск позиции, с которой начинается подстрока
int pos(char *s, char *c, int n)
{
	int i, j;		// Счетчики для циклов
	int lenC, lenS;	// Длины строк
		
	//Находим размеры строки исходника и искомого
	for (lenC = 0; c[lenC]; lenC++);
	for (lenS = 0; s[lenS]; lenS++);

	for (i = 0; i <= lenS - lenC; i++) // Пока есть возможность поиска
	{
		for (j = 0; s[i + j] == c[j]; j++); // Проверяем совпадение посимвольно
		// Если посимвольно совпадает по длине искомого
		// Вернем из функции номер ячейки, откуда начинается совпадение
		// Учитывать 0-терминатор  ( '\0' )
 		if (j - lenC == 1 && i == lenS - lenC && !(n - 1)) return i;
		if (j == lenC)
		if (n - 1) n--; 
		else return i;
	}
	//Иначе вернем -1 как результат отсутствия подстроки
	return -1;
}

int main()
{
	char *s = "parapapa";
	char *c = "pa";

	int i, n = 0;

	for (i = 1; n != -1; i++)
	{
		n = pos(s, c, i);

		if (n >= 0)
			std:: cout << n << std:: endl;
	}
}

#include <iostream>

// Функция для поиска подстроки в строке

// + поиск позиции, с которой начинается подстрока

int pos(char *s, char *c, int n)

{

int i, j; // Счетчики для циклов

int lenC, lenS; // Длины строк

//Находим размеры строки исходника и искомого

for (lenC = 0; c[lenC]; lenC++);

for (lenS = 0; s[lenS]; lenS++);

for (i = 0; i <= lenS - lenC; i++) // Пока есть возможность поиска

{

for (j = 0; s[i + j] == c[j]; j++); // Проверяем совпадение посимвольно

// Если посимвольно совпадает по длине искомого

// Вернем из функции номер ячейки, откуда начинается совпадение

// Учитывать 0-терминатор ( '\0' )

if (j - lenC == 1 && i == lenS - lenC && !(n - 1)) return i;

if (j == lenC)

if (n - 1) n--;

else return i;

}

//Иначе вернем -1 как результат отсутствия подстроки

return -1;

}

int main()

{

char *s = "parapapa";

char *c = "pa";

int i, n = 0;

for (i = 1; n != -1; i++)

{

n = pos(s, c, i);

if (n >= 0)

std:: cout << n << std:: endl;

}

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

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

Подробно об этом

Дело в том, что символы Си-строк хранятся в символьном массиве. Каждая строка характеризуется так называемым ASCIIZ свойством. Эта аббревиатура буквально переводится как «строка, которая оканчивается символом с кодом равным нулю” – аски-зеро.

Подвох состоит в том, что если искомое находится в самом конце строки, придется учитывать и это зеро. Оно тоже является частью строки, и при таком алгоритме еще и совпадает с концом искомой строки.

Например строки: "Remember Harry number room" и "room" на самом деле выглядят как "Remember Harry number room\0" и "room\0" . Где '\0' , символ с кодом 0, который говорит, что строка закончилась. Кстати именно такой подход и позволяет писать такие циклы как:

for (lenC = 0; c[lenC]; lenC++);
for (lenS = 0; s[lenS]; lenS++);

1 2	for (lenC = 0; c[lenC]; lenC++); for (lenS = 0; s[lenS]; lenS++);

Тут c[lenC] и s[lenS] сравниваются с нулевым значением, и их удобно читать как “Увеличивать счетчик, пока есть (не пустой) символ в строке”. Пустым как раз будет считаться последний символ – зеро.

Если мы хотим найти слово room, стоящее в середине слова, нам нужно сравнивать только 4 символа, но если вдруг искомое встретится только в конце – нам нужно уже сравнивать не 4 символа, а… 5 ! Или проверять, не стоит ли после нуль-терминатор этот. В этом нет ничего сложного. К такой строке нужно просто привыкнуть.

Например строки: [crayon-673ef5676088a844444056-i/] и [crayon-673ef5676088b753619853-i/] на самом деле выглядят как [crayon-673ef5676089a329320090-i/] и [crayon-673ef5676089c952023060-i/] . Где [crayon-673ef5676089d091239734-i/] , символ с кодом 0, который говорит, что строка закончилась. Кстати именно такой подход и позволяет писать такие циклы как:

[crayon-673ef5676089f211162995/]

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

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

for (i = 1; n != -1; i++)
{
	n = pos(s, c, i);

	if (n >= 0)
		std:: cout << n << std:: endl;
}

for (i = 1; n != -1; i++)

{

n = pos(s, c, i);

if (n >= 0)

std:: cout << n << std:: endl;

}

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

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

#include <iostream>
#include <string>

using namespace std;

int main()
{
	setlocale(LC_ALL, "rus");
	string s = "Hello world";
	cout << "Найдено в позиции " << s.find("lo") << endl;
}

#include <iostream>

#include <string>

using namespace std;

int main()

{

setlocale(LC_ALL, "rus");

string s = "Hello world";

cout << "Найдено в позиции " << s.find("lo") << endl;

}

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

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

#include <iostream>
#include <string>

using namespace std;

int main()
{
	string s = "parapapa";	
	int i = 0;

	for ( i = s.find("pa", i++); i != string::npos; i = s.find("pa", i + 1))
		cout << i << endl;
}

#include <iostream>

#include <string>

using namespace std;

int main()

{

string s = "parapapa";

int i = 0;

for ( i = s.find("pa", i++); i != string::npos; i = s.find("pa", i + 1))

cout << i << endl;

}

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

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

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

10 thoughts on “Поиск подстроки в строке”

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

Свежие записи

Свежие комментарии

Статистика