Substring Search Patterns in DSA Python - Execution Trace

Concept Flow - Substring Search Patterns

Start: Text and Pattern

↓

Set index i=0 in Text

↓

Compare Pattern with Text[i..i+len(Pattern)-1

↓

Pattern found at i

→Stop or continue

No↓

Increment i by 1

↓

Check if i <= len(Text) - len(Pattern)

Yes↓

Stop: Pattern not found

↩Back to Compare

The search slides the pattern over the text one by one, comparing characters until a match is found or the text ends.

Execution Sample

DSA Python

text = "hello world"
pattern = "lo"
for i in range(len(text) - len(pattern) + 1):
    if text[i:i+len(pattern)] == pattern:
        print(f"Pattern found at index {i}")
        break

This code searches for the substring 'lo' in 'hello world' by checking each possible position.

Execution Table

Step	Operation	Index i	Substring Compared	Match?	Action	Visual State
1	Compare substring	0	"he"	No	Increment i	Text: h e l l o w o r l d Pattern: l o
2	Compare substring	1	"el"	No	Increment i	Text: h e l l o w o r l d Pattern: l o
3	Compare substring	2	"ll"	No	Increment i	Text: h e l l o w o r l d Pattern: l o
4	Compare substring	3	"lo"	Yes	Print index 3 and stop	Text: h e l l o w o r l d Pattern: l o at index 3
5	Stop	-	-	-	Pattern found, search ends	Final State: Pattern found at index 3

💡 Pattern found at index 3, search stops early.

Variable Tracker

Variable	Step 1	Step 2	Step 3	Step 4	After Step 4	Final
i	0	1	2	3	3	3
Substring Compared	"he"	"el"	"ll"	"lo"	"lo"	"lo"
Match?	No	No	No	Yes	Yes	Yes

Key Moments - 3 Insights

Why do we stop the search when i reaches len(text) - len(pattern) + 1?

Because beyond this point, the remaining text is shorter than the pattern, so no full match is possible. See execution_table row 4 where i=3 and pattern length fits.

Why do we compare text[i:i+len(pattern)] instead of just text[i]?

Because we need to check the entire pattern length at each position, not just one character. Execution_table rows 1-4 show substring comparisons of length equal to the pattern.

What happens if the pattern is not found in the text?

The loop completes without a match and the search ends with no output. This is shown by the exit condition in concept_flow when i exceeds the limit.

Visual Quiz - 3 Questions

Look at the execution_table, what substring is compared at step 3?

A "ll"

B "el"

C "lo"

D "he"

💡 Hint

Check the 'Substring Compared' column at step 3 in execution_table.

At which step does the pattern match the substring?

A Step 2

B Step 4

C Step 3

D Step 5

💡 Hint

Look for 'Match?' column showing 'Yes' in execution_table.

If the pattern was "wo", at which index would the match be found?

A Index 4

B Index 5

C Index 6

D Index 7

💡 Hint

Check the text 'hello world' and find where 'wo' starts.

Concept Snapshot

Substring Search Patterns:
- Slide pattern over text from index 0 to len(text)-len(pattern)
- At each index, compare substring of pattern length
- If match, report index and stop or continue
- Stop when no more full pattern fits
- Simple and direct method for substring search

Full Transcript

Substring search means looking for a smaller string inside a bigger string. We start at the beginning of the big string and check if the smaller string matches the characters starting there. If not, we move one step forward and check again. We keep doing this until we find the smaller string or reach the end where the smaller string cannot fit anymore. This method compares substrings of the same length as the pattern at each step. When a match is found, we can stop or continue searching. If no match is found, the search ends after checking all possible positions.

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