Search Algorithms

Searching for a Substring Appearing Multiple Times

How do I handle searching for a substring within a string when the substring can appear multiple times?

Abstract art representing computer programming

To handle searching for a substring that appears multiple times within a string, you can use a loop with the std::string::find() function. This method allows you to locate all occurrences of the substring.

Using a Loop with std::string::find()

Here's an example:

#include <iostream>
#include <string>

int main() {
  std::string text = "This is a test."
    "This test is only a test.";
  std::string target = "test";
  std::size_t pos = text.find(target);

  while (pos != std::string::npos) {
    std::cout << "Found '" << target
      << "' at position " << pos << "\n";
    pos = text.find(target, pos + target.length());  
  }
}
Found 'test' at position 10
Found 'test' at position 20
Found 'test' at position 35

Explanation

  • std::string::find() searches for the first occurrence of the substring.
  • The loop continues searching by updating the position to start just after the last found substring.
  • The loop terminates when std::string::npos (indicating no more occurrences) is returned.

Handling Overlapping Substrings

If the substrings can overlap, adjust the position increment. By incrementing the position by 1, overlapping occurrences are also found:

#include <iostream>
#include <string>

int main() {
  std::string text = "aaa";
  std::string target = "aa";
  std::size_t pos = text.find(target);

  while (pos != std::string::npos) {
    std::cout << "Found '" << target
      << "' at position " << pos << "\n";
    pos = text.find(target, pos + 1);  
  }
}
Found 'aa' at position 0
Found 'aa' at position 1

Using Regular Expressions

For more complex search patterns, consider using std::regex:

#include <iostream>
#include <regex>
#include <string>

int main() {
  std::string text = "test1 test2 test1 test2";
  std::regex pattern("test[0-9]");

  auto words_begin = std::sregex_iterator(
    text.begin(), text.end(), pattern);
  auto words_end = std::sregex_iterator();

  for (auto it = words_begin; it != words_end; ++it) {
    std::smatch match = *it;
    std::cout << "Found '" << match.str()
      << "' at position "
      << match.position() << "\n";
  }
}
Found 'test1' at position 0
Found 'test2' at position 6
Found 'test1' at position 12
Found 'test2' at position 18

Explanation

  • std::regex allows for complex pattern matching.
  • std::sregex_iterator is used to iterate through all matches.

By using these methods, you can effectively search for a substring that appears multiple times within a string, handling both non-overlapping and overlapping cases, as well as more complex patterns.

Answers to questions are automatically generated and may not have been reviewed.

A computer programmer
Part of the course:

Professional C++

Comprehensive course covering advanced concepts, and how to use them on large-scale projects.

Free, unlimited access

This course includes:

  • 124 Lessons
  • 550+ Code Samples
  • 96% Positive Reviews
  • Regularly Updated
  • Help and FAQ
Free, Unlimited Access

Professional C++

Comprehensive course covering advanced concepts, and how to use them on large-scale projects.

Screenshot from Warhammer: Total War
Screenshot from Tomb Raider
Screenshot from Jedi: Fallen Order
Contact|Privacy Policy|Terms of Use
Copyright © 2024 - All Rights Reserved