К сожалению во все времена камнем преткновения для многих начинающих 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*.