String matching basics in Data Structures Theory - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is string matching?

String matching is the process of finding one string (called the pattern) within another string (called the text). It helps identify if and where the pattern appears in the text.

beginner

What is a pattern in string matching?

A pattern is the smaller string or sequence of characters that we want to find inside a larger string (the text).

beginner

Name a simple method to perform string matching.

The simplest method is the 'Naive' approach, which checks for the pattern at every possible position in the text one by one.

beginner

Why is string matching important in real life?

String matching is used in searching text documents, finding words in search engines, DNA sequence analysis, and detecting patterns in data.

intermediate

What is the difference between exact and approximate string matching?

Exact string matching finds the pattern only if it matches perfectly. Approximate string matching allows some differences, useful when there are typos or errors.

What does string matching help you find?

A The number of vowels in a string

B The length of a string

C A smaller string inside a larger string

D The first letter of a string

String matching is about finding a smaller string (pattern) inside a larger string (text).

Which method checks every position in the text to find the pattern?

A Naive method

B Binary search

C Sorting

D Hashing

The naive method tries to match the pattern starting at every position in the text.

What is the 'pattern' in string matching?

A The smaller string to find

B The larger string to search in

C The number of characters

D The position of the match

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

Which of these is NOT a common use of string matching?

A Searching words in documents

B Detecting patterns in data

C DNA sequence analysis

D Calculating the speed of a car

Calculating car speed is unrelated to string matching.

Approximate string matching allows:

A Only perfect matches

B Matches with some differences

C No matches

D Only matches at the start

Approximate matching allows some differences, useful for typos or errors.

Explain what string matching is and why it is useful in everyday technology.

Think about how you find words in a document or search online.

Describe the naive method of string matching and its main drawback.

Imagine looking for a word by checking every spot one by one.

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