Строки C++: поиск подстроки в строке на cpp
К сожалению во все времена камнем преткновения для многих начинающих c++ программистов была работа со строками. Была, есть и, даже после чтения десятков статей подобного содержания, будет. В данном посте я рассматриваю вопрос поиска подстроки в строке. Данный вопрос миллионы раз рассматривался, обсуждался и «переваривался» на форумах, сайтах, блогах, на русском, английском, французском (. ) языках людьми всех возрастов, вероисповеданий, расс. Я тоже хочу ответить на вопрос: «как найти подстроку в строке?» В данном случае мы рассмотрим самый простой вариант — это поиск подстроки в строке типа string. Здесь задача решается одной функцией в 14 строк. Сразу приведу функцию, которую я накидал:
int count_of_substrings(string src, string sub) < int start = 0; int count = 0; int pos = 0; for(;;)< pos = src.find(sub.c_str(),start); if (pos != -1)< start = pos + sub.size(); count++; >else < break; >> return count; >
Рассмотрим каждый момент отдельно. Для поиска подстрок запускаем бесконечный цикл. Это делается т.к. мы не знаем точно сколько вхождений будет. А если бы знали, то и алгоритм нам не нужен был бы. Первым же делом ищем вхождение подстроки в строку. Результат — позиция первого символа подстроки в строке. Т. к. искать начинаем с начала строки, то значение start = 0. Итак, если мы нашли хот одно вхождение, то увеличиваем позицию для начала старта. Приведенная мною формула экономит процессорное время, т.к. пропускает найденную подстроку, и программа в этой части поиск уже не производит. Также мы увеличиваем значение счетчика. И всё! В конце выводим значение счетчика. В следующем посте я приведу НЕСКОЛЬКО быстрых алгоритмов поиска подстроки в строках типа char*.
std:: string::find
Searches the string for the first occurrence of the sequence specified by its arguments.
When pos is specified, the search only includes characters at or after position pos, ignoring any possible occurrences that include characters before pos.
Notice that unlike member find_first_of, whenever more than one character is being searched for, it is not enough that just one of these characters match, but the entire sequence must match.
Parameters
str Another string with the subject to search for. pos Position of the first character in the string to be considered in the search.
If this is greater than the string length, the function never finds matches.
Note: The first character is denoted by a value of 0 (not 1): A value of 0 means that the entire string is searched.
s Pointer to an array of characters.
If argument n is specified (3), the sequence to match are the first n characters in the array.
Otherwise (2), a null-terminated sequence is expected: the length of the sequence to match is determined by the first occurrence of a null character.
n Length of sequence of characters to match. c Individual character to be searched for.
size_t is an unsigned integral type (the same as member type string::size_type ).
Return Value
The position of the first character of the first match.
If no matches were found, the function returns string::npos.
size_t is an unsigned integral type (the same as member type string::size_type ).
Example
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// string::find // std::cout // std::string int main () < std::string str ("There are two needles in this haystack with needles."); std::string str2 ("needle"); // different member versions of find in the same order as above: std::size_t found = str.find(str2); if (found!=std::string::npos) std::cout "first 'needle' found at: " << found '\n'; found=str.find("needles are small",found+1,6); if (found!=std::string::npos) std::cout "second 'needle' found at: " << found '\n'; found=str.find("haystack"); if (found!=std::string::npos) std::cout "'haystack' also found at: " << found '\n'; found=str.find('.'); if (found!=std::string::npos) std::cout "Period found at: " << found '\n'; // let's replace the first needle: str.replace(str.find(str2),str2.length(),"preposition"); std::cout << str '\n'; return 0; >Notice how parameter pos is used to search for a second instance of the same search string. Output:
first 'needle' found at: 14 second 'needle' found at: 44 'haystack' also found at: 30 Period found at: 51 There are two prepositions in this haystack with needles.
Complexity
Unspecified, but generally up to linear in length()-pos times the length of the sequence to match (worst case).
Iterator validity
Data races
Exception safety
If s does not point to an array long enough, it causes undefined behavior.
Otherwise, the function never throws exceptions (no-throw guarantee).
See also
string::rfind Find last occurrence of content in string (public member function) string::find_first_of Find character in string (public member function) string::find_last_of Find character in string from the end (public member function) string::find_first_not_of Find absence of character in string (public member function) string::find_last_not_of Find non-matching character in string from the end (public member function) string::replace Replace portion of string (public member function) string::substr Generate substring (public member function)
std::basic_string:: find
Finds the first substring equal to the given character sequence. Search begins at pos , i.e. the found substring must not begin in a position preceding pos .
2) Finds the first substring equal to the range [ s , s + count ) . This range may contain null characters.
3) Finds the first substring equal to the character string pointed to by s . The length of the string is determined by the first null character using Traits :: length ( s ) .
5) Implicitly converts t to a string view sv as if by std:: basic_string_view < CharT, Traits >sv = t ; , then finds the first substring equal to sv .
Formally, a substring str is said to be found at position xpos if all of the following are true :
In particular, this implies that
Contents
[edit] Parameters
| str | — | string to search for |
| pos | — | position at which to start the search |
| count | — | length of substring to search for |
| s | — | pointer to a character string to search for |
| ch | — | character to search for |
| t | — | object (convertible to std::basic_string_view ) to search for |
[edit] Return value
Position of the first character of the found substring or npos if no such substring is found.
[edit] Exceptions
If an exception is thrown for any reason, this function has no effect (strong exception safety guarantee).
[edit] Example
#include #include #include void print(int id, std::string::size_type n, std::string const& s) { std::cout id ") "; if (std::string::npos == n) std::cout "not found! n == npos\n"; else std::cout "found @ n = " n ", substr(" n ") = " std::quoted(s.substr(n)) '\n'; } int main() { std::string::size_type n; std::string const s = "This is a string"; /* ^ ^ ^ 1 2 3 */ // search from beginning of string n = s.find("is"); print(1, n, s); // search from position 5 n = s.find("is", 5); print(2, n, s); // find a single character n = s.find('a'); print(3, n, s); // find a single character n = s.find('q'); print(4, n, s); } 1) found @ n = 2, substr(2) = "is is a string" 2) found @ n = 5, substr(5) = "is a string" 3) found @ n = 8, substr(8) = "a string" 4) not found! n == npos
[edit] Defect reports
The following behavior-changing defect reports were applied retroactively to previously published C++ standards.
| DR | Applied to | Behavior as published | Correct behavior |
|---|---|---|---|
| LWG 847 | C++98 | there was no exception safety guarantee | added strong exception safety guarantee |
| LWG 2064 | C++11 | overloads (3,4) were noexcept | removed |
| LWG 2946 | C++17 | overload (5) caused ambiguity in some cases | avoided by making it a template |
| P1148R0 | C++11 C++17 | noexcept for overloads (4,5) were accidently dropped by LWG2064/LWG2946 | restored |
Поиск подстроки в строке
Сейчас мы разберём на примерах, как может выглядеть алгоритм поиска подстроки в строке. Примеры будут основываться на функциях стандартных библиотек, ведь именно в таких функциях и проявляются все удобства написания программ. А вот классический разбор алгоритма, основанный на циклах и сравнениях, также достаточно примечателен. Поэтому мы его рассмотрим в этом же уроке.
Сам алгоритм в принципе очень прост. Есть две строки. Например «Hello world» и «lo»
Работать будем в два цикла:
- Первый будет выполнять проход по всей строке, и искать местоположение первой буквы искомой строки ( «lo» ).
- Второй, начиная с найденной позиции первой буквы – сверять, какие буквы стоят после неё и сколько из них подряд совпадают.
Проиллюстрируем поиск подстроки в строке:
На первых двух итерациях цикла сравниваемые буквы не будут совпадать (выделено красным). На третьей итерации искомая буква (первый символ искомого слова) совпала с символом в строке, где происходит поиск. При таком совпадении в работу включается второй цикл.
Он призван отсчитывать количество символов после первого в искомой строке, которые будут совпадать с символами в строке исходной. Если один из следующих символов не совпадает – цикл завершает свою работу. Нет смысла гонять цикл впустую, после первого несовпадения, так как уже понятно, что искомого тут нет.
На третьей итерации совпал только первый символ искомой строки, а вот второй уже не совпадает. Придется первому циклу продолжить работу. Четвертая итерация дает необходимые результаты – совпадают все символы искомой строки с частью исходной строки. А раз все символы совпали – подстрока найдена. Работу алгоритма можно закончить.
Посмотрим, как выглядит классический код поиска подстроки в строке в С++: