Substring Search Patterns in DSA C++ - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to check if the pattern exists in the text using the find() method.

DSA C++

std::string text = "hello world";
std::string pattern = "world";
if (text.[1](pattern) != std::string::npos) {
    std::cout << "Pattern found" << std::endl;
} else {
    std::cout << "Pattern not found" << std::endl;
}

Drag options to blanks, or click blank then click option'

Afind

Breplace

Ccompare

Dsubstr

Attempts:

3 left

💡 Hint

Common Mistakes

Using substr() instead of find() to search for a pattern.

Using compare() which compares strings but does not search for substrings.

The find() method returns the starting index of the pattern if found, otherwise std::string::npos.

2fill in blank

medium

Complete the code to extract the substring from text starting at index 3 with length 4.

DSA C++

std::string text = "substring";
std::string sub = text.[1](3, 4);
std::cout << sub << std::endl;

Drag options to blanks, or click blank then click option'

Afind

Bsubstr

Ccompare

Dreplace

Attempts:

3 left

💡 Hint

Common Mistakes

Using find() which searches for a substring but does not extract it.

Using replace() which modifies the string instead of extracting.

The substr() method extracts a substring starting at the given index with the specified length.

3fill in blank

hard

Fix the error in the code to correctly compare the substring with the pattern.

DSA C++

std::string text = "example";
std::string pattern = "amp";
if (text.substr(2, 3).[1](pattern) == 0) {
    std::cout << "Match found" << std::endl;
} else {
    std::cout << "No match" << std::endl;
}

Drag options to blanks, or click blank then click option'

Acompare

Bfind

Csubstr

Dreplace

Attempts:

3 left

💡 Hint

Common Mistakes

Using find() which returns index, not a comparison result.

Using substr() incorrectly inside the if condition.

The compare() method returns 0 if the two strings are equal.

4fill in blank

hard

Fill both blanks to create a loop that finds all occurrences of pattern in text.

DSA C++

std::string text = "abracadabra";
std::string pattern = "abra";
size_t pos = 0;
while ((pos = text.[1](pattern, pos)) != std::string::npos) {
    std::cout << "Found at " << pos << std::endl;
    pos [2] pattern.length();
}

Drag options to blanks, or click blank then click option'

Afind

B+=

C-=

Dreplace

Attempts:

3 left

💡 Hint

Common Mistakes

Using replace() instead of find() in the loop condition.

Using -= instead of += causing infinite loop or wrong position.

Use find() to locate the pattern starting from pos, then increment pos by pattern length to continue searching.

5fill in blank

hard

Fill all three blanks to create a map of each word to its length for words longer than 3 characters.

DSA C++

std::vector<std::string> words = {"code", "is", "fun", "and", "powerful"};
std::map<std::string, int> lengths;
for (const auto& word : words) {
    if (word.[2]() [3] 3) {
        lengths[word] = [1];
    }
}

Drag options to blanks, or click blank then click option'

Aword.length()

Blength

C>

D<=

Attempts:

3 left

💡 Hint

Common Mistakes

Using <=' instead of > causing wrong filtering.

Using word.length without parentheses causing syntax error.

Use word.length() to get length, call length() method on word, and compare with > 3 to filter longer words.

Practice

1. What is the main goal of substring search algorithms in strings?

easy

A. To count the number of vowels in a string

B. To sort the characters of a string alphabetically

C. To reverse the entire string

D. To find if a smaller string exists inside a larger string

Solution

1. Step 1: Understand substring search purpose

   Substring search algorithms check if a smaller string (pattern) appears inside a bigger string (text).

2. Step 2: Compare options with definition

   Only To find if a smaller string exists inside a larger string describes finding a smaller string inside a larger one, which matches substring search.

3. Final Answer:

   To find if a smaller string exists inside a larger string -> Option D

4. Quick Check:

   Substring search = find smaller string inside larger [OK]

Hint: Substring search means finding a smaller string inside a bigger one [OK]

Common Mistakes:

• Confusing substring search with sorting or reversing strings
• Thinking substring search counts characters instead of finding patterns

2. Which of the following is the correct syntax to check if string pattern is a substring of string text in C++?

easy

A. if (text.find(pattern) != std::string::npos) { /* found */ }

B. if (pattern.contains(text)) { /* found */ }

C. if (text.indexOf(pattern)) { /* found */ }

D. if (text.search(pattern) == true) { /* found */ }

Solution

1. Step 1: Recall C++ substring search syntax

   In C++, std::string::find returns the position of the substring or std::string::npos if not found.

2. Step 2: Analyze each option

   if (text.find(pattern) != std::string::npos) { /* found */ } uses text.find(pattern) != std::string::npos, which is correct. Others use invalid or non-existent methods.

3. Final Answer:

   if (text.find(pattern) != std::string::npos) { /* found */ } -> Option A

4. Quick Check:

   Use find() and compare with npos [OK]

Hint: Use text.find(pattern) != npos to check substring [OK]

Common Mistakes:

• Using methods like contains or indexOf which don't exist in std::string
• Comparing find() result directly to true or false

3. What will be the output of the following C++ code?

std::string text = "hello world";
std::string pattern = "world";
size_t pos = text.find(pattern);
if (pos != std::string::npos) {
    std::cout << pos << std::endl;
} else {
    std::cout << -1 << std::endl;
}

medium

A. 5

B. -1

C. 6

D. 0

Solution

1. Step 1: Find substring position in text

   The substring "world" starts at index 6 in "hello world" (counting from 0).

2. Step 2: Check condition and output

   Since find returns 6 (not npos), the code prints 6.

3. Final Answer:

   6 -> Option C

4. Quick Check:

   "world" starts at index 6 in "hello world" [OK]

Hint: Remember string indices start at 0 in C++ [OK]

Common Mistakes:

• Counting index starting at 1 instead of 0
• Printing -1 when substring is actually found

4. Identify the error in this substring search code snippet:

std::string text = "example";
std::string pattern = "amp";
if (text.find(pattern) == -1) {
    std::cout << "Not found" << std::endl;
} else {
    std::cout << "Found" << std::endl;
}

medium

A. Comparing find() result to -1 instead of std::string::npos

B. Using std::cout incorrectly

C. Pattern string is empty

D. Missing semicolon after if statement

Solution

1. Step 1: Understand find() return value

   std::string::find returns std::string::npos if substring not found, not -1.

2. Step 2: Identify incorrect comparison

   Comparing to -1 is wrong; must compare to std::string::npos for correctness.

3. Final Answer:

   Comparing find() result to -1 instead of std::string::npos -> Option A

4. Quick Check:

   Use npos, not -1, to check find() failure [OK]

Hint: Always compare find() result with std::string::npos [OK]

Common Mistakes:

• Using -1 instead of std::string::npos for not found
• Assuming find() returns boolean

5. Given a large text and multiple patterns, which substring search approach is best to efficiently find all pattern occurrences?

// Patterns: ["he", "she", "his", "hers"]
// Text: "ahishers"

hard

A. Use Rabin-Karp algorithm with hashing for each pattern

B. Build an Aho-Corasick automaton for all patterns and search once

C. Use naive search for each pattern separately

D. Use std::string::find in a loop for each pattern

Solution

1. Step 1: Understand multiple pattern search problem

   Searching many patterns separately is inefficient; better to search all at once.

2. Step 2: Identify best algorithm for multiple patterns

   Aho-Corasick builds a combined automaton to find all patterns in one pass efficiently.

3. Step 3: Compare other options

   Naive and Rabin-Karp per pattern or repeated find calls are slower for many patterns.

4. Final Answer:

   Build an Aho-Corasick automaton for all patterns and search once -> Option B

5. Quick Check:

   Multiple patterns = Aho-Corasick automaton [OK]

Hint: Use Aho-Corasick for multiple pattern substring search [OK]

Common Mistakes:

• Using naive search for each pattern separately
• Applying single-pattern algorithms repeatedly
• Ignoring combined automaton approach