Search substring in string C ++

Now we will look at examples, search algorithm might look for a substring within a string. Examples are based on the standard library functions, it is in these functions, and have all the amenities of writing programs. But the classic parsing algorithm, based on loops and comparisons, It is also quite remarkable. Therefore, we will consider it in the same lesson.

The algorithm itself is very simple in principle,. There are two strings. For example "Hello world" and "the"

Work will be in two loops:

The first will be to carry out a passage across the string, and look for location first letter search string ( "the" ).
Second, since the position of the first letter found – check, which letters are after it, and how many of them match in a row.

We illustrate searching for a substring within a string:

The first two iterations of the loop compared the letters would not be the same (marked in red). The third iteration of the desired letter (the first character of the desired word) It coincides with the character in the string, where the search. In this match the work included the second loop.

It is designed to count the number of characters after the first in the search string, which will coincide with the characters in the original string. If one of the symbols do not match – Loop exits. It makes no sense to chase the loop of wasted, after the first discrepancy, since it is already clear, that there is no title.

In the third iteration matched only the first character of the string, but the second is not the same. The first loop will have to continue. The fourth iteration gives the required results – match all the characters of the string with a portion of the source string. And since all the characters matched – substring found. Algorithm work can be completed.

We will see, It looks like a classic substring search code string in C ++:

#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;

}

Two loops performed each his task. One stomping on the string hoping to find “head” search word (first character). The second finds, whether there is found after “head” “body” sought. And checks, whether it does not lie “body” at the end of the string. That is. is not found if the word length is one more than the required length of the string, considering, Null terminator that falls into this unit ( '' ).

We see, what program found begin substringhowever, in the cells of the character array index 0 and 4. But why? After all, in a wordParapapa 3 such substring. The thing '' .

More about this

The thing is, that the symbols of the C strings are stored in a character array. Each line is characterized by the so-called property ASCIIZ. This abbreviation is literally translated as "string, which ends with the character code zero” – aski-zero.

The catch is that, if desired it is at the end of the line, It has to be taken into account and it is zero. It is also part of the line, and this algorithm also coincides with the end of the string.

For example the line: [crayon-6622367e74e47245851583-i/] and [crayon-6622367e74e49990606132-i/] actually look like [crayon-6622367e74e4c058882261-i/] and [crayon-6622367e74e4e615990629-i/] . Where [crayon-6622367e74e51312616796-i/] , with the code symbol 0, who says, that the string has ended. By the way this approach and allows you to write such cycles as:

[crayon-6622367e74e53594008561/]

Herec[Excellence] and s[lenS] compared with a zero value, and easy to read as a “Increase count, while there is (not empty) character in a string”. Empty just be considered the last character - zero.

If we want to find the word room, Standing in the middle of a word, we need only compare 4 symbols, but if suddenly required to meet only at the end – we should not have to compare 4 symbols, and… 5 ! Or check, not whether after this null terminator. This is no big deal. By this line just need to get used to.

In general, the meaning of the algorithm ends here. No more difficulties than zero at the end of the line there. However, should pay attention to the multiplicity of search. What, if we need to find the string in several positions?

How many times the search term occurs in the string and in what places? It is designed to control and the third parameter – int n – number of occurrences of a string. If you put the unit back – He finds the first match title. If a deuce, it will make the first loop to skip first found, and seek a second. If three – look for the third and so on. Each search term found, occurrences of this counter is decremented. This allows us to describe the search loop:

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;

}

That is, to find the first, second, third, fourth match… As long as the function does not return -1, that indicate the absence of N-tion of the title in a string.

Now, for comparison, search for a substring in a string ++ hederom 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;

}

It is all! Loop string C ++ is provided by find(), returns the number of the cell, which begins with the body of the search string in the source string. Result:

How the multiplicity? Yes please:

#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;

}

Function find() takes second parameter symbol number, from which to start search. That is. When you find the first occurrence of, its value is incremented and find() search continues with the next character after the head found. Result: