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

Recall & Review

beginner

What is the main goal of substring search in strings?

To find if a smaller string (pattern) exists inside a larger string (text) and locate its position(s).

beginner

Explain the naive substring search approach.

Check every position in the text to see if the pattern matches starting there. Simple but can be slow for large texts.

intermediate

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

Use information from previous matches to avoid rechecking characters, by precomputing a prefix table to skip unnecessary comparisons.

intermediate

What does the prefix table (also called 'lps' array) represent in KMP?

For each position in the pattern, it stores the length of the longest proper prefix which is also a suffix up to that position.

intermediate

Why is KMP more efficient than the naive approach?

Because it never moves the search index in the text backward, avoiding repeated comparisons and achieving linear time complexity.

What does the naive substring search algorithm do?

A Checks every position in the text for the pattern

B Uses a prefix table to skip comparisons

C Sorts the text before searching

D Uses hashing to find the pattern

The naive approach checks every position in the text to see if the pattern matches starting there.

What is the purpose of the prefix table in KMP?

A To store the pattern characters

B To skip unnecessary comparisons by storing longest prefix-suffix lengths

C To reverse the pattern

D To count pattern occurrences

The prefix table stores the longest proper prefix which is also a suffix to help skip comparisons.

Which of these is true about KMP algorithm?

A It only works for numeric strings

B It has quadratic time complexity

C It sorts the text before searching

D It uses a prefix table to achieve linear time complexity

KMP uses a prefix table to avoid rechecking characters, achieving linear time complexity.

In substring search, what is a 'pattern'?

A The smaller string to find

B The larger string to search in

C A sorting algorithm

D A data structure

The pattern is the smaller string we want to find inside the larger text.

Which substring search method is simplest but least efficient?

A KMP algorithm

B Rabin-Karp algorithm

C Naive search

D Boyer-Moore algorithm

Naive search is the simplest method but can be slow for large texts.

Describe how the Knuth-Morris-Pratt (KMP) algorithm improves substring search efficiency.

Think about how KMP uses pattern information to skip ahead.

Explain the difference between naive substring search and KMP algorithm.

Focus on how each method handles repeated comparisons.

Practice

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

easy

A. To sort characters in a string alphabetically

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

C. To reverse the order of characters in a string

D. To count the total number of characters in a string

Solution

1. Step 1: Understand substring search goal

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

2. Step 2: Compare with other options

   Sorting, reversing, and counting characters are different string operations unrelated to substring search.

3. Final Answer:

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

4. Quick Check:

   Substring search = find smaller string inside bigger string [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
• Assuming substring search changes the string

2. Which of the following is the correct way to check if string text contains substring pattern in C#?

easy

A. bool found = Contains(text, pattern);

B. bool found = text.Find(pattern);

C. bool found = text.Contains(pattern);

D. bool found = text.Index(pattern);

Solution

1. Step 1: Recall C# string method for substring check

   The correct method to check if a string contains another is Contains, called on the string instance.

2. Step 2: Validate method usage

   text.Contains(pattern) returns a boolean indicating if pattern is inside text. Other options are invalid or do not exist.

3. Final Answer:

   bool found = text.Contains(pattern); -> Option C

4. Quick Check:

   Use Contains method on string to check substring [OK]

Hint: Use text.Contains(pattern) to check substring presence [OK]

Common Mistakes:

• Using non-existent methods like Find or Index
• Calling Contains as a standalone function
• Confusing method names or parameters

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

string text = "hello world";
string pattern = "wor";
bool result = text.Contains(pattern);
Console.WriteLine(result);

medium

A. True

B. Runtime exception

C. Compilation error

D. False

Solution

1. Step 1: Check if pattern "wor" is in text "hello world"

   The substring "wor" appears starting at index 6 in "hello world".

2. Step 2: Evaluate Contains method result

   Since the substring exists, text.Contains(pattern) returns true, so result is true.

3. Final Answer:

   True -> Option A

4. Quick Check:

   Substring "wor" in "hello world" = true [OK]

Hint: Check if substring is inside text literally to get true/false [OK]

Common Mistakes:

• Assuming Contains returns index instead of bool
• Thinking substring is not present due to partial match
• Confusing output with string printing

4. Identify the error in the following C# code snippet for substring search:

string text = "data structures";
string pattern = "struct";
int index = text.IndexOf(pattern);
if (index)
{
    Console.WriteLine("Found at " + index);
}

medium

A. The if condition should check if index >= 0

B. IndexOf method does not exist for strings

C. Pattern variable is not declared

D. Console.WriteLine syntax is incorrect

Solution

1. Step 1: Understand IndexOf return value

   IndexOf returns the starting index of the substring or -1 if not found.

2. Step 2: Check if condition usage

   The if condition if (index) is invalid because index is an int, not a boolean. It should check index >= 0 to confirm substring found.

3. Final Answer:

   The if condition should check if index >= 0 -> Option A

4. Quick Check:

   Check index >= 0 to confirm substring found [OK]

Hint: Check if index >= 0 to confirm substring found [OK]

Common Mistakes:

• Using int directly as boolean in if condition
• Assuming IndexOf returns boolean
• Ignoring negative index meaning not found

5. Given a list of strings words and a pattern string p, which approach best finds all words containing p as a substring efficiently in C#?

hard

A. Use words.IndexOf(p) directly

B. Sort the list and use binary search for the pattern

C. Replace all occurrences of p in each word with empty string

D. Use a loop to check each word with word.Contains(p) and collect matches

Solution

1. Step 1: Understand substring search in multiple strings

   To find all words containing p, we must check each word individually for the substring.

2. Step 2: Evaluate options for efficiency and correctness

   Using a loop with word.Contains(p) is straightforward and efficient. Sorting and binary search do not help substring search. words.IndexOf(p) is invalid because words is a list of strings, not a string. Replacing substrings does not find matches.

3. Final Answer:

   Use a loop to check each word with word.Contains(p) and collect matches -> Option D

4. Quick Check:

   Loop + Contains per word finds all substring matches [OK]

Hint: Loop through words and use Contains to find substring matches [OK]

Common Mistakes:

• Trying binary search for substring matching
• Using IndexOf on list instead of strings
• Replacing substrings instead of checking presence