String matching basics in Data Structures Theory - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

Understanding the Naive String Matching Algorithm

What is the main drawback of the naive string matching algorithm when searching for a pattern in a text?

A It requires preprocessing the pattern which takes extra time

B It can have a worst-case time complexity proportional to the product of text and pattern lengths

C It only works for patterns shorter than the text

D It uses extra memory proportional to the size of the text

💡 Hint

Think about how many comparisons the naive method might do in the worst case.

The naive algorithm checks for the pattern at every position in the text, which can lead to many repeated comparisons, resulting in a worst-case time complexity of O(n*m), where n is the text length and m is the pattern length.

📋 Factual

intermediate

Output of a Simple String Matching Check

Given the text "abracadabra" and the pattern "cada", what will be the output of a function that returns the starting index of the first occurrence of the pattern in the text, or -1 if not found?

Data Structures Theory

text = "abracadabra"
pattern = "cada"

# Function returns index or -1
result = text.find(pattern)
print(result)

A 3

B -1

C 4

D 5

💡 Hint

Look carefully at where the pattern starts in the text.

The substring "cada" starts at index 4 in "abracadabra" (0-based indexing), so the function returns 4.

🔍 Analysis

advanced

Comparing String Matching Algorithms by Efficiency

Which string matching algorithm improves efficiency by using information from previous character comparisons to avoid unnecessary re-checks?

A Naive string matching algorithm

B Random search algorithm

C Brute force search

D Knuth-Morris-Pratt (KMP) algorithm

💡 Hint

Consider which algorithm uses a prefix table to skip ahead.

The KMP algorithm preprocesses the pattern to create a prefix table that helps it skip unnecessary comparisons, improving efficiency over naive methods.

❓ Reasoning

advanced

Determing the Number of Matches

How many times does the pattern "ana" appear in the text "banana" when overlapping matches are counted?

A 2

B 1

C 3

D 0

💡 Hint

Check for matches starting at each character, including overlaps.

The pattern "ana" appears twice in "banana": starting at index 1 and index 3 (0-based), counting overlapping occurrences.

❓ Comparison

expert

Identifying the Correct Output of a Pattern Search with Wildcards

Consider a pattern matching function that supports the wildcard character "?" which matches any single character. Given the text "abcdefg" and the pattern "a?c?e?g", what is the output of the function that returns true if the pattern matches the text exactly, and false otherwise?

A true

B false

C SyntaxError

D RuntimeError

💡 Hint

Check each character match considering that '?' can match any single character.

The pattern "a?c?e?g" matches the text "abcdefg" because each '?' matches the characters 'b', 'd', and 'f' respectively, resulting in a full match.

Practice

1. What is the main goal of string matching in computer science?

easy

A. To sort a list of strings alphabetically

B. To find if a smaller text appears inside a bigger text

C. To count the number of characters in a string

D. To convert a string to uppercase

Solution

1. Step 1: Understand the definition of string matching

   String matching is about checking if a smaller text (pattern) exists inside a larger text (text).

2. Step 2: Compare options with the definition

   Only To find if a smaller text appears inside a bigger text describes this goal correctly; others describe different string operations.

3. Final Answer:

   To find if a smaller text appears inside a bigger text -> Option B

4. Quick Check:

   String matching = find smaller text inside bigger text [OK]

Hint: Remember: string matching means searching for a pattern inside text [OK]

Common Mistakes:

• Confusing string matching with sorting strings
• Thinking string matching counts characters
• Mixing string matching with case conversion

2. Which of the following is the correct way to check if the string pattern exists in text using Python?

easy

A. if pattern in text:

B. if text contains pattern:

C. if text has pattern:

D. if pattern inside text:

Solution

1. Step 1: Recall Python syntax for substring check

   In Python, the correct syntax to check if one string is inside another is using the in keyword.

2. Step 2: Evaluate each option

   Only if pattern in text: uses the correct Python syntax. Options A, B, and D are not valid Python statements.

3. Final Answer:

   if pattern in text: -> Option A

4. Quick Check:

   Python substring check uses 'in' keyword [OK]

Hint: Use 'in' keyword to check substring in Python [OK]

Common Mistakes:

• Using incorrect keywords like 'contains' or 'has'
• Writing invalid syntax like 'inside'
• Confusing method calls with keywords

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

text = "hello world"
pattern = "world"
print(pattern in text)

medium

A. False

B. world

C. True

D. Error

Solution

1. Step 1: Understand the 'in' operator in Python

   The expression pattern in text checks if the string 'world' is inside 'hello world'.

2. Step 2: Check if 'world' is a substring of 'hello world'

   Since 'world' appears at the end of 'hello world', the expression returns True.

3. Final Answer:

   True -> Option C

4. Quick Check:

   'world' in 'hello world' = True [OK]

Hint: Check if substring is exactly inside the main string [OK]

Common Mistakes:

• Assuming output is the substring itself
• Confusing True/False output
• Expecting an error due to syntax

4. Identify the error in the following code snippet for string matching:

text = "data structures"
pattern = "structure"
if pattern in text:
print("Found")

medium

A. Indentation error in the print statement

B. Wrong variable names used

C. Incorrect string matching operator

D. Missing quotation marks around pattern

Solution

1. Step 1: Check Python syntax for if statement

   Python requires the code inside an if block to be indented properly.

2. Step 2: Inspect the print statement indentation

   The print statement is not indented, causing an indentation error.

3. Final Answer:

   Indentation error in the print statement -> Option A

4. Quick Check:

   Python blocks need indentation [OK]

Hint: Indent code inside if statements properly [OK]

Common Mistakes:

• Ignoring indentation rules in Python
• Assuming 'in' operator is wrong
• Changing variable names unnecessarily

5. You want to find all starting positions where the pattern "ana" appears in the text "banana". Which of the following lists shows the correct starting indices (0-based)?

hard

A. [1, 2, 3]

B. [0, 2, 4]

C. [2, 4]

D. [1, 3]

Solution

1. Step 1: Identify occurrences of 'ana' in 'banana'

   Check each substring of length 3 in 'banana': 'ban'(0), 'ana'(1), 'nan'(2), 'ana'(3), 'na'(4 incomplete).

2. Step 2: List starting indices where substring matches 'ana'

   'ana' appears starting at index 1 and index 3.

3. Final Answer:

   [1, 3] -> Option D

4. Quick Check:

   Positions of 'ana' in 'banana' = [1, 3] [OK]

Hint: Slide window over text to find all pattern starts [OK]

Common Mistakes:

• Counting overlapping matches incorrectly
• Using 1-based instead of 0-based indices
• Missing one of the occurrences