Substring Search Patterns in DSA Python - 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 possible position in the text where the pattern could start and compare characters one by one until a match is found or all positions are checked.

intermediate

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

Use information from previous character matches to avoid rechecking characters, by precomputing a longest prefix suffix (LPS) array.

intermediate

What does the LPS (Longest Prefix Suffix) 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 avoids re-examining characters that have already been matched, leading to a time complexity of O(n + m) instead of O(n*m), where n is text length and m is pattern length.

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

A O(n*m)

B O(n + m)

C O(n)

D O(m)

The naive approach checks each position in the text and compares up to m characters, leading to O(n*m) in the worst case.

In KMP, what does the LPS array help to avoid?

A Rechecking characters that matched before

B Searching the entire text again

C Comparing characters in the pattern

D Building the pattern string

The LPS array helps KMP skip rechecking characters that have already matched, improving efficiency.

Which substring search algorithm uses a precomputed table to skip characters?

A Naive Search

B Bubble Sort

C KMP Algorithm

D Binary Search

KMP uses the LPS table to skip unnecessary comparisons.

If the pattern is 'ABABC', what is the LPS value at index 4 (0-based)?

A 3

B 1

C 2

D 0

The LPS array for 'ABABC' is [0, 0, 1, 2, 0]. At index 4, it is 0, as no proper prefix matches the suffix.

Which of these is NOT a substring search algorithm?

A Rabin-Karp

B Merge Sort

C KMP

D Naive Search

Merge Sort is a sorting algorithm, not used for substring search.

Describe how the naive substring search algorithm works step-by-step.

Think about sliding the pattern over the text and comparing characters.

Explain the purpose and construction of the LPS array in the KMP algorithm.

Focus on how pattern prefixes relate to suffixes.

Practice

1. What does the in operator check when used like 'abc' in 'abcdef' in Python?

easy

A. If the substring 'abc' exists anywhere inside the string 'abcdef'

B. If the string 'abcdef' starts with 'abc'

C. If the string 'abcdef' ends with 'abc'

D. If the strings 'abc' and 'abcdef' are exactly equal

Solution

1. Step 1: Understand the in operator for strings

   The in operator checks if the left string is found anywhere inside the right string.

2. Step 2: Apply to given strings

   Since 'abc' is at the start of 'abcdef', it is found inside it.

3. Final Answer:

   If the substring 'abc' exists anywhere inside the string 'abcdef' -> Option A

4. Quick Check:

   'abc' in 'abcdef' = True [OK]

Hint: Remember: 'in' checks anywhere inside the string [OK]

Common Mistakes:

• Thinking 'in' only checks start of string
• Confusing 'in' with equality
• Assuming 'in' checks only end of string

2. Which of the following is the correct syntax to find the index of substring 'cat' in string s = 'concatenate' using Python?

easy

A. s.indexOf('cat')

B. find(s, 'cat')

C. s.find('cat')

D. index(s, 'cat')

Solution

1. Step 1: Recall Python string method for substring index

   Python strings have a method called find() to locate substring index.

2. Step 2: Check method usage

   The correct syntax is s.find('cat'). Other options are invalid in Python.

3. Final Answer:

   s.find('cat') -> Option C

4. Quick Check:

   Use string.find(substring) syntax [OK]

Hint: Use string.find(substring) to get index [OK]

Common Mistakes:

• Using non-Python syntax like indexOf
• Calling find as a standalone function
• Confusing method name or order of arguments

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

text = 'abracadabra'
pos = text.find('ra')
print(pos)

medium

A. 2

B. 1

C. 3

D. -1

Solution

1. Step 1: Understand find() method behavior

   The find() method returns the lowest index where the substring is found or -1 if not found.

2. Step 2: Locate substring 'ra' in 'abracadabra'

   The substring 'ra' first appears starting at index 1 (abracadabra).

3. Final Answer:

   1 -> Option B

4. Quick Check:

   First 'ra' at index 1 [OK]

Hint: Remember: find() returns first occurrence index [OK]

Common Mistakes:

• Assuming find() returns all occurrences
• Confusing index with count
• Mistaking find() return -1 for found substring

4. Identify the error in the following code snippet that tries to check if substring 'dog' is in string s:

s = 'hotdog'
if s.contains('dog'):
    print('Found')
else:
    print('Not Found')

medium

A. The method contains does not exist for strings in Python

B. The substring 'dog' is misspelled

C. The string s is not defined

D. The print statements are incorrect

Solution

1. Step 1: Check string method availability in Python

   Python strings do not have a contains() method; membership is checked with in.

2. Step 2: Correct way to check substring presence

   Use 'dog' in s instead of s.contains('dog').

3. Final Answer:

   The method contains does not exist for strings in Python -> Option A

4. Quick Check:

   Use in operator, not contains() [OK]

Hint: Use in for substring check, not contains() [OK]

Common Mistakes:

• Using Java-like contains() method in Python
• Misspelling substring or variable
• Assuming print syntax is wrong

5. Given a string s = 'banana', which code snippet correctly finds all starting indices of substring 'ana' in s?

hard

A. indices = [s.find('ana')]

B. indices = [i for i in range(len(s)) if 'ana' in s[i]]

C. indices = [i for i in range(len(s)) if s.find('ana') == i]

D. indices = [i for i in range(len(s)) if s[i:i+3] == 'ana']

Solution

1. Step 1: Understand substring search for all occurrences

   To find all starting indices, check each position if substring matches.

2. Step 2: Analyze each option

   indices = [i for i in range(len(s)) if s[i:i+3] == 'ana'] uses slicing and compares substring at each index correctly. indices = [s.find('ana')] finds only first occurrence. indices = [i for i in range(len(s)) if s.find('ana') == i] incorrectly compares find() result to index. indices = [i for i in range(len(s)) if 'ana' in s[i]] incorrectly checks membership of substring in single character.

3. Final Answer:

   indices = [i for i in range(len(s)) if s[i:i+3] == 'ana'] -> Option D

4. Quick Check:

   Slice and compare at each index for all matches [OK]

Hint: Use slicing and loop to find all substring start indices [OK]

Common Mistakes:

• Using find() only returns first match
• Comparing find() result incorrectly
• Checking substring in single character