String Pattern Matching Naive in DSA Typescript - Execution Trace

Concept Flow - String Pattern Matching Naive

Start at text index i=0

↓

Compare pattern with text from i

↓

Match all pattern chars?

Yes→Pattern found at i

No↓

Increment i by 1

↓

Check if i <= text length - pattern length

Yes↓

End search

↩Back to Compare

Start matching pattern from each position in text until end is reached or pattern is found.

Execution Sample

DSA Typescript

function naiveSearch(text: string, pattern: string): number[] {
  const result = [];
  for (let i = 0; i <= text.length - pattern.length; i++) {
    let j = 0;
    while (j < pattern.length && text[i + j] === pattern[j]) j++;
    if (j === pattern.length) result.push(i);
  }
  return result;
}

This code finds all starting indices where pattern matches text using naive search.

Execution Table

Step	Operation	Text Index i	Pattern Index j	Match Check	Action	Matches Found	Visual State
1	Start outer loop	0	-	-	Check pattern at text[0]	[]	Text: 'ABABAB' Pattern: 'ABA'
2	Compare chars	0	0	text[0]='A' == pattern[0]='A'	j=1	[]	Matching at i=0, j=0
3	Compare chars	0	1	text[1]='B' == pattern[1]='B'	j=2	[]	Matching at i=0, j=1
4	Compare chars	0	2	text[2]='A' == pattern[2]='A'	j=3	[]	Matching at i=0, j=2
5	Pattern matched	0	3	j == pattern.length	Add i=0 to result	[0]	Match found at index 0
6	Increment i	1	-	-	Check pattern at text[1]	[0]	Moving to i=1
7	Compare chars	1	0	text[1]='B' != pattern[0]='A'	No match, move i	[0]	Mismatch at i=1, j=0
8	Increment i	2	-	-	Check pattern at text[2]	[0]	Moving to i=2
9	Compare chars	2	0	text[2]='A' == pattern[0]='A'	j=1	[0]	Matching at i=2, j=0
10	Compare chars	2	1	text[3]='B' == pattern[1]='B'	j=2	[0]	Matching at i=2, j=1
11	Compare chars	2	2	text[4]='A' == pattern[2]='A'	j=3	[0]	Matching at i=2, j=2
12	Pattern matched	2	3	j == pattern.length	Add i=2 to result	[0,2]	Match found at index 2
13	Increment i	3	-	-	Check pattern at text[3]	[0,2]	Moving to i=3
14	Compare chars	3	0	text[3]='B' != pattern[0]='A'	No match, move i	[0,2]	Mismatch at i=3, j=0
15	Increment i	4	-	-	Check pattern at text[4]	[0,2]	Moving to i=4
16	Compare chars	4	0	text[4]='A' == pattern[0]='A'	j=1	[0,2]	Matching at i=4, j=0
17	Compare chars	4	1	text[5]='B' == pattern[1]='B'	j=2	[0,2]	Matching at i=4, j=1
18	Compare chars	4	2	text[6]=undefined != pattern[2]='A'	No match, move i	[0,2]	Mismatch at i=4, j=2 (text ended)
19	Increment i	5	-	-	i > text.length - pattern.length, stop	[0,2]	End search
20	Return result	-	-	-	-	[0,2]	Matches at indices 0 and 2

💡 i reached 5 which is > text.length - pattern.length (6 - 3 = 3), so search ends

Variable Tracker

Variable	Start	After Step 5	After Step 12	After Step 20
i	0	0	2	5
j	-	3	3	-
result	[]	[0]	[0,2]	[0,2]

Key Moments - 3 Insights

Why do we stop checking pattern characters when a mismatch is found?

Because as shown in steps 7 and 14, once a mismatch occurs, continuing to check further characters is unnecessary and inefficient. We immediately move to the next text index i.

Why does the outer loop stop when i > text.length - pattern.length?

At step 19, we see that if i is greater than text length minus pattern length, the pattern cannot fit anymore, so the search ends to avoid out-of-bound errors.

Why do we add i to result only when j equals pattern length?

At steps 5 and 12, when j reaches the pattern length, it means all pattern characters matched successfully starting at index i, so we record that index.

Visual Quiz - 3 Questions

Look at the execution table at step 4. What is the value of j after this step?

A 2

B 1

C 3

D 0

💡 Hint

Check the 'Pattern Index j' and 'Action' columns at step 4 in the execution table.

At which step does the first pattern match get added to the result array?

A Step 3

B Step 7

C Step 5

D Step 12

💡 Hint

Look for the step where 'Add i=0 to result' appears in the 'Action' column.

If the pattern was 'AB' instead of 'ABA', how would the final matches found change?

A Matches would be at indices [1, 3, 5]

B Matches would be at indices [0, 2, 4]

C Matches would be at indices [0, 1, 2]

D Matches would be at indices [0, 3]

💡 Hint

Consider how many times 'AB' appears in 'ABABAB' and compare with the variable_tracker results.

Concept Snapshot

Naive String Pattern Matching:
- Check pattern at every text index i
- Compare characters one by one (j)
- If mismatch, move i forward
- If full pattern matches (j == pattern length), record i
- Stop when i > text length - pattern length

Full Transcript

This visualization shows how naive string pattern matching works by checking the pattern at each position in the text. We start at index i=0 and compare each character of the pattern with the text. If all characters match, we record the index. If a mismatch occurs, we move to the next index i. The process continues until the pattern cannot fit in the remaining text. The execution table tracks each comparison and match found, while the variable tracker shows how i, j, and the result array change over time. Key moments clarify why we stop early on mismatch and when to stop the search. The quiz tests understanding of these steps.

Practice

1. What does the naive string pattern matching algorithm do?

easy

A. It sorts the text before searching for the pattern.

B. It uses a hash function to find the pattern quickly.

C. It checks every possible position in the text to find the pattern.

D. It uses a tree structure to match the pattern.

Solution

1. Step 1: Understand naive pattern matching

   The naive algorithm tries to match the pattern starting at each position in the text one by one.

2. Step 2: Compare with other methods

   Unlike hashing or trees, naive does not use extra data structures or preprocessing.

3. Final Answer:

   It checks every possible position in the text to find the pattern. -> Option C

4. Quick Check:

   Naive = check all positions [OK]

Hint: Naive means try all positions one by one [OK]

Common Mistakes:

• Confusing naive with hashing or advanced algorithms
• Thinking it sorts text before matching
• Assuming it uses trees or graphs

2. Which of the following is the correct syntax to start a loop from 0 to text.length - pattern.length in TypeScript for naive pattern matching?

easy

A. for (let i = 0; i < pattern.length; i++)

B. for (let i = 1; i < text.length - pattern.length; i++)

C. for (let i = 0; i < text.length; i++)

D. for (let i = 0; i <= text.length - pattern.length; i++)

Solution

1. Step 1: Determine loop range for matching

   The loop must start at 0 and go up to text.length - pattern.length inclusive to check all valid positions.

2. Step 2: Check syntax correctness

   for (let i = 0; i <= text.length - pattern.length; i++) uses <= and correct boundaries, others either start at 1 or wrong limits.

3. Final Answer:

   for (let i = 0; i <= text.length - pattern.length; i++) -> Option D

4. Quick Check:

   Loop from 0 to text.length - pattern.length inclusive [OK]

Hint: Loop till text length minus pattern length inclusive [OK]

Common Mistakes:

• Starting loop at 1 instead of 0
• Looping beyond valid range causing errors
• Using pattern length as loop limit

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

const text = "abcabcabc";
const pattern = "abc";
let count = 0;
for (let i = 0; i <= text.length - pattern.length; i++) {
  let j = 0;
  while (j < pattern.length && text[i + j] === pattern[j]) {
    j++;
  }
  if (j === pattern.length) {
    count++;
  }
}
console.log(count);

medium

A. 3

B. 2

C. 1

D. 0

Solution

1. Step 1: Identify pattern occurrences in text

   The pattern "abc" appears at positions 0, 3, and 6 in the text "abcabcabc".

2. Step 2: Count matches using the loop

   The code increments count each time the pattern matches fully, so count becomes 3.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Pattern "abc" occurs 3 times [OK]

Hint: Count matches by checking each position fully [OK]

Common Mistakes:

• Counting overlapping matches incorrectly
• Stopping after first match
• Off-by-one errors in loop

4. Find the error in this naive pattern matching code snippet:

const text = "hellohello";
const pattern = "lo";
for (let i = 0; i < text.length - pattern.length; i++) {
  let j = 0;
  while (j < pattern.length && text[i + j] === pattern[j]) {
    j++;
  }
  if (j === pattern.length) {
    console.log(i);
  }
}

medium

A. The while condition should use || instead of &&.

B. The loop should use <= instead of < to include last position.

C. The pattern length is incorrect.

D. The console.log should be outside the loop.

Solution

1. Step 1: Check loop boundary for matching

   The loop ends at text.length - pattern.length - 1 due to < operator, missing last valid position.

2. Step 2: Correct loop condition

   Changing < to <= includes the last position where pattern can match.

3. Final Answer:

   The loop should use <= instead of < to include last position. -> Option B

4. Quick Check:

   Loop boundary must cover all valid start indices [OK]

Hint: Use <= to cover last possible start index [OK]

Common Mistakes:

• Using < instead of <= in loop
• Changing && to || in while condition
• Misplacing console.log outside loop

5. Given a text and a pattern, how can you modify the naive string pattern matching algorithm to count overlapping occurrences of the pattern in the text? For example, text = "aaaaa" and pattern = "aaa" should return 3.

hard

A. After finding a match, move the start index by 1 instead of pattern length.

B. After finding a match, move the start index by pattern length.

C. Use a hash function to detect overlaps.

D. Skip checking overlapping positions to improve speed.

Solution

1. Step 1: Understand overlapping matches

   Overlapping means matches can start inside a previous match, so we must check every position.

2. Step 2: Adjust index increment after match

   Instead of jumping by pattern length, increment start index by 1 to check next position for overlaps.

3. Final Answer:

   After finding a match, move the start index by 1 instead of pattern length. -> Option A

4. Quick Check:

   Increment by 1 to count overlaps [OK]

Hint: Move start by 1 after match to count overlaps [OK]

Common Mistakes:

• Skipping positions after match causing missed overlaps
• Using hash functions unnecessarily
• Trying to skip overlaps to speed up