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 inside 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, moving one by one until it finds a match or reaches the end.

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, so it doesn't start over from scratch after a mismatch.

intermediate

What does the 'prefix function' or 'lps array' represent in KMP?

It stores the length of the longest proper prefix of the pattern that is also a suffix for each position, helping to decide where to continue matching after a mismatch.

advanced

Why is the Boyer-Moore algorithm efficient for substring search?

Because it compares the pattern from right to left and uses two rules to skip sections of the text, reducing the number of comparisons needed.

What does the naive substring search algorithm do when a mismatch occurs?

A Moves the pattern one position to the right and starts matching from the beginning of the pattern.

B Uses a precomputed table to skip some positions.

C Starts matching from the last matched character.

D Stops searching immediately.

The naive approach simply shifts the pattern by one and restarts matching from the first character.

In KMP, what is the purpose of the lps (longest prefix suffix) array?

A To skip characters in the text after a mismatch.

B To remember how much of the pattern matched so far to avoid rechecking.

C To store the pattern characters.

D To reverse the pattern.

The lps array helps KMP know where to continue matching in the pattern after a mismatch.

Which substring search algorithm compares characters from right to left in the pattern?

A Naive search

B KMP algorithm

C Rabin-Karp algorithm

D Boyer-Moore algorithm

Boyer-Moore compares the pattern from right to left to optimize skipping.

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

A O(n log m)

B O(n + m)

C O(n * m)

D O(m^2)

Naive search can check every position and every character, leading to O(n * m) in the worst case.

Which algorithm uses hashing to find substrings efficiently?

A Rabin-Karp

B Naive search

C Boyer-Moore

D KMP

Rabin-Karp uses hashing to quickly compare substring values.

Describe how the KMP algorithm improves substring search compared to the naive approach.

Think about how KMP avoids rechecking characters after a mismatch.

Explain the main differences between the naive, KMP, and Boyer-Moore substring search algorithms.

Focus on how each algorithm handles mismatches and skips.