Substring Search Patterns in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Naive Substring Search

What is the output of the following C++ code that searches for all occurrences of a pattern in a text using the naive substring search method?

DSA C++

std::string text = "abracadabra";
std::string pattern = "abra";
for (int i = 0; i <= (int)text.size() - (int)pattern.size(); i++) {
    int j = 0;
    while (j < (int)pattern.size() && text[i + j] == pattern[j]) {
        j++;
    }
    if (j == (int)pattern.size()) {
        std::cout << i << " ";
    }
}
std::cout << std::endl;

A 0 3 7

B 7

C 3 7

D 0 7

💡 Hint

Check where the pattern "abra" fully matches in the text "abracadabra".

The pattern "abra" appears at index 0 and again at index 7 in the text. The naive search checks each position and prints indices where full match occurs.

❓ Predict Output

intermediate

Output of KMP Prefix Table Construction

What is the output of the prefix table (also called lps array) constructed by the KMP algorithm for the pattern "ababc"?

DSA C++

std::string pattern = "ababc";
int n = pattern.size();
std::vector<int> lps(n, 0);
int len = 0;
int i = 1;
while (i < n) {
    if (pattern[i] == pattern[len]) {
        len++;
        lps[i] = len;
        i++;
    } else {
        if (len != 0) {
            len = lps[len - 1];
        } else {
            lps[i] = 0;
            i++;
        }
    }
}
for (int x : lps) std::cout << x << " ";
std::cout << std::endl;

A 0 0 0 1 2

B 0 1 2 0 0

C 0 0 1 2 0

D 0 1 0 1 0

💡 Hint

The prefix table stores the length of the longest proper prefix which is also suffix for each prefix of the pattern.

For pattern "ababc", the lps array is [0,0,1,2,0]. This means at index 2, the longest prefix-suffix length is 1, at index 3 it is 2, and so on.

🧠 Conceptual

advanced

Time Complexity of Rabin-Karp Algorithm

Which of the following best describes the average and worst-case time complexity of the Rabin-Karp substring search algorithm when searching for a pattern of length m in a text of length n?

A Average: O(n*m), Worst-case: O(n+m)

B Average: O(n+m), Worst-case: O(n*m)

C Average: O(n^2), Worst-case: O(n^2)

D Average: O(m), Worst-case: O(n)

💡 Hint

Consider how hashing helps average case but collisions cause worst case.

Rabin-Karp uses hashing to find matches quickly on average (O(n+m)). However, in worst case, many hash collisions cause it to check all substrings, leading to O(n*m).

❓ Predict Output

advanced

Output of Boyer-Moore Bad Character Table

What is the output of the bad character table for the pattern "example" assuming ASCII characters and the table stores the last occurrence index of each character in the pattern?

DSA C++

std::string pattern = "example";
const int ALPHABET_SIZE = 256;
std::vector<int> badChar(ALPHABET_SIZE, -1);
for (int i = 0; i < (int)pattern.size(); i++) {
    badChar[(unsigned char)pattern[i]] = i;
}
std::cout << badChar['e'] << " " << badChar['x'] << " " << badChar['a'] << " " << badChar['m'] << " " << badChar['p'] << " " << badChar['l'] << " " << badChar['z'] << std::endl;

A 6 1 2 3 4 5 -1

B 0 1 2 3 4 5 -1

C 6 0 2 3 4 5 -1

D 6 1 0 3 4 5 -1

💡 Hint

The bad character table stores the last index of each character in the pattern.

In "example", 'e' appears last at index 6, 'x' at 1, 'a' at 2, 'm' at 3, 'p' at 4, 'l' at 5, and 'z' does not appear (-1).

🧠 Conceptual

expert

Choosing Substring Search Algorithm for Large Texts

You need to search for multiple patterns in a very large text efficiently. Which substring search approach is best suited for this scenario?

A Build an Aho-Corasick automaton for all patterns and search once through the text.

B Use Rabin-Karp algorithm for each pattern with rolling hash.

C Use the Knuth-Morris-Pratt (KMP) algorithm for each pattern separately.

D Use the naive substring search for each pattern separately.

💡 Hint

Consider an algorithm designed for multiple pattern searches simultaneously.

Aho-Corasick builds a trie automaton for all patterns and searches the text once, efficiently finding all pattern occurrences. Other methods search separately, which is inefficient for many patterns.

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