Substring Search Patterns in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main goal of substring search algorithms?

To find the position(s) where a smaller string (pattern) appears within a larger string (text).

beginner

Explain the naive substring search approach.

It checks every possible position in the text to see if the pattern matches starting there, comparing characters one by one.

intermediate

What is the key idea behind the Knuth-Morris-Pratt (KMP) algorithm?

KMP uses a precomputed table to skip unnecessary comparisons by remembering how the pattern matches against itself.

intermediate

How does the Rabin-Karp algorithm speed up substring search?

It uses a rolling hash to quickly compare the pattern's hash with substrings' hashes in the text, reducing character-by-character checks.

beginner

What is the worst-case time complexity of the naive substring search?

O(n*m), where n is the length of the text and m is the length of the pattern.

Which substring search algorithm uses a prefix table to avoid rechecking characters?

A Naive search

B Boyer-Moore

C Rabin-Karp

D Knuth-Morris-Pratt (KMP)

KMP builds a prefix table to skip unnecessary comparisons.

What technique does Rabin-Karp use to quickly compare substrings?

A Prefix table

B Binary search

C Rolling hash

D Suffix array

Rabin-Karp uses a rolling hash to compare substring hashes efficiently.

In the naive substring search, what happens when a mismatch occurs?

A The pattern shifts by one position and comparison restarts

B The algorithm stops

C The pattern shifts by the length of the pattern

D The pattern shifts by the length of the text

Naive search shifts the pattern by one and restarts comparison after mismatch.

Which algorithm is best suited for multiple pattern searches simultaneously?

A Naive search

B Aho-Corasick (not covered here)

C Rabin-Karp

D KMP

Aho-Corasick is designed for multiple pattern searches efficiently.

What is the average time complexity of KMP algorithm?

A O(n + m)

B O(n*m)

C O(m^2)

D O(n^2)

KMP runs in linear time relative to text and pattern lengths.

Describe how the Knuth-Morris-Pratt (KMP) algorithm improves substring search compared to the naive approach.

Think about how KMP remembers previous matches to avoid rechecking.

Explain the role of hashing in the Rabin-Karp substring search algorithm.

Consider how hashes help avoid checking every character.

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