Substring Search Patterns in DSA Javascript - Execution Trace

Concept Flow - Substring Search Patterns

Start at index 0 in text

↓

Compare substring with text segment

↓

Record match

↓

Check if end of text reached

No↓

Repeat comparison

Yes↓

Done

Start comparing the substring at each index of the text. If it matches, record the position. Move forward until the text end.

Execution Sample

DSA Javascript

const text = 'hellohello';
const pattern = 'llo';
for(let i = 0; i <= text.length - pattern.length; i++) {
  if(text.substring(i, i + pattern.length) === pattern) {
    console.log(i);
  }
}

Search for the substring 'llo' inside 'hellohello' and print all starting indices where it matches.

Execution Table

Step	Index i	Text Segment Compared	Match?	Action	Output Indices Found So Far
1	0	'hel'	No	Move to next index	[]
2	1	'ell'	No	Move to next index	[]
3	2	'llo'	Yes	Record index 2	[2]
4	3	'loh'	No	Move to next index	[2]
5	4	'ohe'	No	Move to next index	[2]
6	5	'hel'	No	Move to next index	[2]
7	6	'ell'	No	Move to next index	[2]
8	7	'llo'	Yes	Record index 7	[2,7]
9	8	'lo'	No	Move to next index	[2,7]
10	9	'o'	No	Move to next index	[2,7]
11	10	End of search	-	Stop	[2,7]

💡 Index 10 exceeds text length - pattern length, so search ends.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	After Step 9	After Step 10	Final
i	0	1	2	3	4	5	6	7	8	9	10	10
Output Indices	[]	[]	[2]	[2]	[2]	[2]	[2]	[2,7]	[2,7]	[2,7]	[2,7]	[2,7]

Key Moments - 3 Insights

Why do we stop the loop at text.length - pattern.length?

Because beyond that index, the remaining text is shorter than the pattern, so no full match is possible. See execution_table step 11 where index 10 ends the search.

Why do we compare text.substring(i, i + pattern.length) instead of just one character?

Because we need to check the whole pattern length at each position to find a full match, not just a single character. Execution_table shows comparing 3 characters each time.

What happens if the pattern is empty?

If pattern length is zero, substring comparisons always match empty string, so matches would be found at every index. This is a special case not shown here.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of 'i' when the first match is found?

A 2

B 0

C 7

D 8

💡 Hint

Check the 'Index i' column where 'Match?' is 'Yes' for the first time.

At which step does the search stop according to the execution_table?

A Step 7

B Step 11

C Step 8

D Step 10

💡 Hint

Look for the row where 'Action' is 'Stop' and 'Index i' indicates end of search.

If the pattern was 'hel' instead of 'llo', which index would be recorded first?

A 7

B 2

C 0

D No match

💡 Hint

Consider the substring at index 0 in the text and compare with 'hel'.

Concept Snapshot

Substring Search Pattern:
- Loop from i=0 to text.length - pattern.length
- At each i, compare text substring of pattern length
- If match, record index i
- Stop when no more full pattern fits
- Prints all start indices where pattern occurs

Full Transcript

This visual trace shows how substring search works by sliding over the text and comparing segments equal to the pattern length. At each step, the substring from the current index is compared to the pattern. If they match, the index is recorded. The loop stops when the remaining text is shorter than the pattern. The example searches for 'llo' in 'hellohello' and finds matches at indices 2 and 7.

Practice

1. What does the indexOf method do when used on a string in JavaScript?

easy

A. Converts the string to uppercase

B. Replaces a substring with another string

C. Splits the string into an array of substrings

D. Finds the position of the first occurrence of a substring

Solution

1. Step 1: Understand the purpose of indexOf

   The indexOf method searches a string for a specified substring and returns the position of its first occurrence.

2. Step 2: Confirm behavior on strings

   If the substring is found, it returns the zero-based index; if not found, it returns -1.

3. Final Answer:

   Finds the position of the first occurrence of a substring -> Option D

4. Quick Check:

   indexOf = position of substring [OK]

Hint: Remember: indexOf returns position or -1 if not found [OK]

Common Mistakes:

• Confusing indexOf with replace method
• Thinking indexOf splits the string
• Assuming indexOf changes the string case

2. Which of the following is the correct syntax to check if the substring 'cat' exists in the string text using includes method?

easy

A. text.include('cat')

B. includes(text, 'cat')

C. text.includes('cat')

D. text.contains('cat')

Solution

1. Step 1: Recall the correct method name

   The correct method to check substring presence is includes, called on the string object.

2. Step 2: Verify syntax

   The syntax is string.includes(substring), so text.includes('cat') is correct.

3. Final Answer:

   text.includes('cat') -> Option C

4. Quick Check:

   Correct method call syntax = text.includes('cat') [OK]

Hint: Use string.includes(substring) to check presence [OK]

Common Mistakes:

• Using wrong method name like include or contains
• Calling includes as a standalone function
• Passing arguments in wrong order

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

const text = 'hello world';
const pos = text.indexOf('o');
console.log(pos);

medium

A. 4

B. 5

C. -1

D. 6

Solution

1. Step 1: Identify the string and substring

   The string is 'hello world' and the substring searched is 'o'.

2. Step 2: Find the first occurrence of 'o'

   Counting from zero: h(0) e(1) l(2) l(3) o(4) (space 5) w(6) o(7). The first 'o' is at index 4.

3. Step 3: Verify the output

   The code uses indexOf('o') which returns the first occurrence index, which is 4.

4. Final Answer:

   4 -> Option A

5. Quick Check:

   First 'o' index = 4 [OK]

Hint: Count string index from zero to find first substring position [OK]

Common Mistakes:

• Counting index starting from 1 instead of 0
• Confusing second 'o' position with first
• Assuming indexOf returns -1 if substring exists

4. The following code is intended to check if the substring 'test' exists in str. What is the error?

const str = 'this is a test';
if (str.indexOf == 'test') {
  console.log('Found');
} else {
  console.log('Not Found');
}

medium

A. The variable str is not declared properly

B. indexOf is used without parentheses, so it compares function to string

C. The if condition should use === instead of ==

D. The substring 'test' is misspelled

Solution

1. Step 1: Analyze the use of indexOf

   The code uses str.indexOf without parentheses, so it refers to the function itself, not the result of calling it.

2. Step 2: Understand the comparison

   Comparing a function to a string ('test') is always false, so the condition is incorrect.

3. Final Answer:

   indexOf is used without parentheses, so it compares function to string -> Option B

4. Quick Check:

   Missing parentheses on indexOf causes error [OK]

Hint: Always call indexOf with parentheses and substring argument [OK]

Common Mistakes:

• Forgetting parentheses on indexOf
• Using wrong comparison operator
• Assuming indexOf returns boolean directly

5. You want to find all starting positions of the substring 'ana' in the string 'banana'. Which approach correctly finds all positions?

hard

A. Use a loop with indexOf and update the start position after each find

B. Use includes repeatedly until it returns false

C. Use lastIndexOf to find all positions from the end

D. Use replace to remove substring and count occurrences

Solution

1. Step 1: Understand the problem of multiple occurrences

   To find all positions, you must repeatedly search starting after the last found position.

2. Step 2: Use a loop with indexOf and update start

   Use indexOf('ana', start) in a loop, updating start to position + 1 each time until no more found.

3. Final Answer:

   Use a loop with indexOf and update the start position after each find -> Option A

4. Quick Check:

   Loop + indexOf with updated start = all positions [OK]

Hint: Loop with indexOf(start) to find all substring positions [OK]

Common Mistakes:

• Using includes which returns only true/false
• Using lastIndexOf which finds only last occurrence
• Using replace which changes string and loses positions