Why this matters
Many programs need to answer one question about text: does this word appear in that text, and if so, where? A search box checks whether the typed words appear in a document. An editor highlights every match of the word you are looking for. A log tool finds lines that contain an error code. Each of these is a substring search: a pattern (the short text you look for) is searched for inside a longer text.
The simplest way to search is to try every starting position in the text and check whether the pattern matches there. This is called the naive method. It is naive because it does no clever shortcuts. It is still the right place to start, because it is easy to check, it is correct, and it shows the cost of searching in plain numbers. Later courses cover faster methods. This lesson covers the simple one, counts its work, and then shows the functions in the C++ standard library that do the same job.
The lesson before this one covered splitting text into fields, which uses a similar character-by-character loop. This lesson does not repeat that material. It focuses on positions and on counting comparisons.
The idea: slide the pattern across the text
Think of a strip of paper with the pattern written on it. Hold the strip over the text, with its first letter over the first letter of the text. Read across and check each letter. If a letter differs, slide the strip one step to the right and start again. If every letter matches, you have found the pattern at that position.
Here is a small example. The text is cabcd and the pattern is bc. The text has five letters, positions 0 to 4, and the pattern has two letters.
- Position 0: the text letter is
c, the pattern letter isb. They differ, so stop and slide. - Position 1: the text letter is
a, which differs fromb. Slide. - Position 2: the text letter is
band matches. Now check the second letter. The text letter iscand the pattern letter isc. They match, and the pattern is complete. The answer is position 2.
The pattern can start at any position where it still fits. If the text has n letters and the pattern has m letters, the last position where the pattern can start is n - m. Positions run from 0 to n - m inclusive, which is n - m + 1 positions in total.
Example 1: the search in C++
The function below returns the first position where the pattern appears, or -1 if it does not appear. It also counts every letter comparison, because the count is the reason for the lesson.
#include <iostream>
#include <string>
using namespace std;
// Returns the index where pattern first appears in text, or -1.
// comparisons counts every character comparison made.
int naiveFind(const string& text, const string& pattern, int& comparisons) {
comparisons = 0;
int n = (int)text.size();
int m = (int)pattern.size();
for (int start = 0; start + m <= n; start++) {
int j = 0;
while (j < m) {
comparisons++;
if (text[start + j] != pattern[j]) {
break;
}
j++;
}
if (j == m) {
return start;
}
}
return -1;
}The outer loop, for (int start = 0; start + m <= n; start++), tries each starting position. The condition start + m <= n means the pattern still fits inside the text from that point. This is the same as start <= n - m, but the form used here avoids a problem with unsigned numbers (numbers that cannot be negative), which the mistakes section explains.
The inner loop compares one pattern letter at a time, starting from the first. The variable j counts how many letters have matched so far. When a letter differs, break leaves the inner loop, and the outer loop moves to the next start. When j reaches m, every letter matched, so the function returns start.
The parameter int& comparisons is a reference. A reference is another name for a variable that exists elsewhere. Changing comparisons inside the function changes the variable in the caller. This lets the function report its work without a second return value.
Now a small driver shows the result for a few inputs.
void run(const string& text, const string& pattern) {
int comparisons = 0;
int at = naiveFind(text, pattern, comparisons);
cout << "text=\"" << text << "\" pattern=\"" << pattern << "\"\n";
cout << " index: " << at << ", comparisons: " << comparisons << "\n";
}
int main() {
run("hello world", "world");
run("hello world", "xyz");
run("aaaaaaaaaa", "aaaab");
run("aaaaaaaaaa", "aaaaa");
}Compile and run it:
g++ -std=c++20 -Wall -o ss1 ss1.cpp
./ss1The output on g++ 15.2 is:
text="hello world" pattern="world"
index: 6, comparisons: 11
text="hello world" pattern="xyz"
index: -1, comparisons: 9
text="aaaaaaaaaa" pattern="aaaab"
index: -1, comparisons: 30
text="aaaaaaaaaa" pattern="aaaaa"
index: 0, comparisons: 5Check the first line by hand. The text hello world has 11 letters and the pattern world has 5, so starts run from 0 to 6, which is 7 starts. Starts 0 to 5 each fail on the first letter, which is 6 comparisons. Start 6 matches all five letters, which is 5 more. The total is 11, and the program agrees.
The second line has no match. The pattern xyz has three letters, so there are 9 starts, from 0 to 8, against 11 letters. Each start fails on its first letter, so the total is 9. The program prints 9.
Example 2: counting the worst case
The third line is the worst case for this method. The text is ten a letters, and the pattern is aaaab. Every start matches the first four letters and fails on the fifth, because the text never has a b.
The number of starts is n - m + 1. Here n is 10 and m is 5, so there are 6 starts. Each start makes m comparisons, which is 5, before it fails on the last letter. The total is (n - m + 1) * m, which is 6 * 5 = 30.
The formula is worth testing on bigger inputs. The program below counts the worst case for four text lengths with a six-letter pattern.
int main() {
string pattern = "aaaaab";
for (int n : {10, 20, 40, 80}) {
string text(n, 'a');
int c = 0;
int at = naiveFind(text, pattern, c);
cout << "n=" << n << " m=" << pattern.size() << " index=" << at
<< " comparisons=" << c << " formula=" << (n - (int)pattern.size() + 1) * (int)pattern.size() << "\n";
}
}The output is:
n=10 m=6 index=-1 comparisons=30 formula=30
n=20 m=6 index=-1 comparisons=90 formula=90
n=40 m=6 index=-1 comparisons=210 formula=210
n=80 m=6 index=-1 comparisons=450 formula=450Two things stand out. The count matches the formula every time. And when the text doubles in length, the count roughly doubles too, because the pattern length is fixed. In this case the cost grows with the number of starts times the pattern length. If the pattern is also long, both numbers matter. A pattern of 1000 letters in a text of 1,000,000 letters has about a billion comparisons in this worst case, which can take a noticeable time on a slow machine.
The best case is different. If the first letter of the pattern is rare in the text, most starts fail at once. The text hello world searched for xyz made one comparison per start, which is the best case in practice.
The naive method is fast enough for short patterns and everyday text, and it is simple to test. It becomes slow when the same long pattern is searched many times in a very long text.
Example 3: a second example with a real sentence
The next example uses a sentence with repeated words, so the search has to move past several false starts before it finds the match.
int main() {
string text = "the cat sat on the mat";
int c = 0;
cout << "index of \"the\": " << naiveFind(text, "the", c) << " comparisons: " << c << "\n";
cout << "index of \"mat\": " << naiveFind(text, "mat", c) << " comparisons: " << c << "\n";
}The output is:
index of "the": 0 comparisons: 3
index of "mat": 19 comparisons: 22The first search matches at position 0, so it makes 3 comparisons and stops. The second search has to pass the t in the, the c in cat and many other starts before it reaches mat at position 19. Those starts cost 22 comparisons in total, which is more than the length of the pattern. Each start that fails on its first letter costs one comparison, and each start that matches part of the pattern costs a few more.
Try to predict the count before you run the code. A good habit is to write down the number of starts first, then add the comparisons from each start.
Example 4: tracing each start
A trace is a record of every step, written down as the code runs. Tracing by hand is the best way to check that you understand the loop. The next program prints one line per start for the text abcabd and the pattern abd. It stops at the first match, so the output shows every step that matters.
int main() {
string text = "abcabd";
string pattern = "abd";
int n = (int)text.size();
int m = (int)pattern.size();
int total = 0;
for (int start = 0; start + m <= n; start++) {
int j = 0;
while (j < m) {
total++;
if (text[start + j] != pattern[j]) break;
j++;
}
cout << "start " << start << ": matched " << j << " letter(s), total so far " << total << "\n";
if (j == m) {
cout << "found at " << start << "\n";
break;
}
}
}The output is:
start 0: matched 2 letter(s), total so far 3
start 1: matched 0 letter(s), total so far 4
start 2: matched 0 letter(s), total so far 5
start 3: matched 3 letter(s), total so far 8
found at 3The word "matched" here means the number of letters that agreed before the first difference. At start 0, the text has a and b where the pattern has a and b, and then c where the pattern has d. That is two matches and one failed comparison, so three comparisons in total. At start 1 the text letter b already differs from the pattern letter a, so it costs one comparison and no letters match. Start 2 works the same way with c. At start 3 the text is abd, which matches all three letters, so it costs three comparisons and the search ends.
The total of 8 comparisons is the number of steps the naive method took. The three failed starts, 0, 1 and 2, cost 5 of those 8 comparisons, and the successful start cost 3. Looking at a trace like this shows where the cost comes from, and it is the same reasoning used for the worst case in Example 2.
The standard library: find and search
The C++ standard library already has search functions, so you do not need to write your own loop in real code. You do need to understand what they do, because they are the tools you will call.
The method most people use is find, a member function of std::string. A member function is a function that belongs to an object and is called with a dot. The name find is the C++ word for the operation. Some other languages call it indexOf, and C++ does not have a method with that name.
#include <iostream>
#include <string>
using namespace std;
int main() {
string text = "hello world, hello again";
size_t p1 = text.find("hello");
size_t p2 = text.find("hello", 1);
size_t p3 = text.find("bye");
cout << "find: " << p1 << " " << p2 << " " << (p3 == string::npos) << "\n";
cout << "npos as int: " << (int)p3 << "\n";
}The output is:
find: 0 13 1
npos as int: -1find returns the position of the first match, which is 0 for the first hello. The second argument, 1, tells find where to start looking, so it skips the first match and returns 13. This second argument is how you find every match in a loop.
When there is no match, find returns string::npos. This is a special value meaning "not a position", and it is the largest value a size_t can hold. The last line of the output shows that converting it to int gives -1. The idea of -1 for "not found" comes from the function you wrote above, and the standard uses npos instead. Compare with string::npos, not with -1.
The standard library also has a general search function, std::search, in the <algorithm> header. It works on any pair of iterators, which are objects that move through a sequence. It is more flexible, because the text does not have to be a std::string. Its default method is the same kind of loop as the naive method above.
#include <algorithm>
#include <functional>
#include <iostream>
#include <string>
using namespace std;
int main() {
string text = "hello world, hello again";
string pattern = "hello";
auto it = search(text.begin(), text.end(), pattern.begin(), pattern.end());
cout << "std::search: " << (it - text.begin()) << "\n";
auto it2 = search(text.begin(), text.end(), boyer_moore_searcher(pattern.begin(), pattern.end()));
cout << "boyer_moore_searcher: " << (it2 - text.begin()) << "\n";
}The output is:
std::search: 0
boyer_moore_searcher: 0The first call uses the default method. The second call passes boyer_moore_searcher, a searcher object added in C++17. It uses a different method that can skip more positions when a letter does not match. Both return an iterator to the first match. The expression it - text.begin() converts the iterator into a position by counting how many letters lie between the start of the text and the match.
Use find for almost all text searches in C++. Use std::search when the text is not a single string, or when you want to choose the searcher. Use the hand-written method when you are learning or when you need the comparison count.
Common mistakes
Comparing the result of find with -1. The find function returns a size_t, which cannot be negative. The "not found" value is string::npos, which is a huge positive number. Writing if (pos == -1) happens to work for many compilers, because -1 is converted to the same huge number, but g++ with -Wall reports it as a sign-comparison warning. Write if (pos == string::npos).
Treating position 0 as false. The code below was meant to test whether hello is in the text. It does the opposite:
#include <iostream>
#include <string>
using namespace std;
int main() {
string text = "hello world, hello again";
if (text.find("hello")) {
cout << "found, wrong test\n";
} else {
cout << "test says not found\n";
}
}The output is:
test says not foundThe match is at position 0, and 0 is false when used as a condition, so the test says "not found" even though the text contains the word. The fix is to compare with string::npos, as in if (text.find("hello") != string::npos).
Going past the end of the text. The naive loop must stop at the last position where the pattern fits. If you write the bound as n - m with unsigned numbers and the pattern is longer than the text, the subtraction wraps around to a very large number, and the loop runs far past the end. The program below shows what happens with substr:
#include <iostream>
#include <string>
using namespace std;
int main() {
string text = "ab";
string pattern = "abc";
size_t n = text.size();
size_t m = pattern.size();
for (size_t s = 0; s <= n - m; s++) {
if (text.substr(s, m) == pattern) {
cout << "found at " << s << "\n";
}
}
cout << "done\n";
}The text has 2 letters and the pattern has 3, so n - m should be negative. With unsigned numbers it becomes a huge number instead, and the loop runs until substr throws. The output on g++ 15.2 is:
terminate called after throwing an instance of 'std::out_of_range'
what(): basic_string::substr: __pos (which is 3) > this->size() (which is 2)The message names the bad position, 3, and the size of the text, 2. The fix is to check m <= n before the loop, or to write the bound as start + m <= n, as Example 1 does.
Forgetting the starting position in a loop. To find every match, you call find again with a start position just past the last match. If you pass the same position each time, the loop finds the same match forever. Exercise 3 below shows the loop with the correct start position, and the answer explains the choice.
Counting overlapping matches by accident. The text aaaa contains the pattern aa three times if matches are allowed to overlap, at positions 0, 1 and 2. A loop that moves forward by the pattern length finds only two. Decide what your problem means before you write the loop.
Practice
Exercise 1. The text is abcabcabc and the pattern is abd. Use the naive method by hand. How many starts are there, and how many comparisons does the search make in total? Confirm with the function from Example 1.
Show the answer
The text has 9 letters and the pattern has 3, so there are 7 starts, from 0 to 6. Start 0 matches ab and then fails on c against d, which is 3 comparisons. Start 1 matches nothing at first, b against a, so 1 comparison. The same pattern repeats: starts 3 and 6 each cost 3 comparisons, and starts 1, 2, 4 and 5 each cost 1 comparison. The total is 3 + 1 + 1 + 3 + 1 + 1 + 3 = 13. The function returns -1, and the count is 13. Check the number with the program before you trust it.
Exercise 2. Write a function int countOccurrences(const string& text, const string& pattern) that counts every position where the pattern starts, including overlapping matches. Test it on aaaa with aa, which should return 3.
Show the answer
int countOccurrences(const string& text, const string& pattern) {
int count = 0;
int n = (int)text.size();
int m = (int)pattern.size();
for (int start = 0; start + m <= n; start++) {
if (text.compare(start, m, pattern) == 0) {
count++;
}
}
return count;
}The loop moves one position at a time, so matches that share letters are all counted. The function compare returns 0 when the two strings are equal. The starts for aaaa are 0, 1 and 2, and all three match, so the result is 3. The compare version is shorter, and it checks the same positions as the hand-written loop.
Exercise 3. Using find with a start position, count the non-overlapping occurrences of one in one two one three one. Explain why the loop should move the start position by the pattern length, not by 1, when you want non-overlapping matches.
Show the answer
string text = "one two one three one";
int count = 0;
size_t pos = text.find("one");
while (pos != string::npos) {
count++;
pos = text.find("one", pos + 3);
}The result is 3. The pattern one has 3 letters, so the next search starts 3 positions after the last match and cannot reuse its letters. Moving the start by 1 would allow matches that share letters, which is the overlapping case from Exercise 2. The pattern one cannot overlap itself, so both methods give 3 for this text, but the rule matters for patterns such as aa.
Exercise 4. For a text of length 1000 and a pattern of length 100, how many comparisons does the naive method make in the worst case? Use the formula (n - m + 1) * m.
Show the answer
The formula gives (1000 - 100 + 1) * 100 = 901 * 100 = 90100. The worst case needs every start to match the pattern up to the last letter, as in the aaaaab example. Real text is rarely this bad, but the formula is the upper limit you can use when you need to reason about the cost.
Exercise 5. Write a function bool containsWord(const string& text, const string& word) that returns true only when the word appears as a whole word, not inside a longer word. Test it on category with the word cat, which should return false, and on the cat sat with cat, which should return true. Assume words are separated by spaces.
Show the answer
bool containsWord(const string& text, const string& word) {
size_t pos = text.find(word);
while (pos != string::npos) {
bool startOk = (pos == 0) || text[pos - 1] == ' ';
size_t end = pos + word.size();
bool endOk = (end == text.size()) || text[end] == ' ';
if (startOk && endOk) {
return true;
}
pos = text.find(word, pos + 1);
}
return false;
}The function finds each raw match, then checks the letter before and the letter after it. A match inside category fails the check on the left or right, so the loop moves on. The search with pos + 1 makes sure every start is tried. For the cat sat, the match at position 4 has a space before it and after it, so the result is true.
Summary
- A naive substring search tries each starting position from 0 to
n - mand compares the pattern letter by letter. - The worst case makes
(n - m + 1) * mcomparisons, which grows with both the text and the pattern length. - The best case is cheap when the first letter of the pattern rarely appears in the text.
std::string::findreturns the first match position, orstring::nposwhen there is no match. Compare withnpos, not with 0 or -1.std::searchin<algorithm>works on iterators, andboyer_moore_searcheris an optional faster method.- Write loop bounds as
start + m <= nto avoid unsigned underflow when the pattern is longer than the text.