String Pattern Matching Naive in DSA Javascript - 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→Record match at i

No↓

Increment i by 1

↓

Is i <= text length - pattern length?

Yes→Repeat compare

No↓

End

Start from the beginning of the text, compare the pattern character by character. If all match, record the position. Move one step forward and repeat until the pattern cannot fit.

Execution Sample

DSA Javascript

function naiveSearch(text, pattern) {
  let matches = [];
  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) {
      matches.push(i);
    }
  }
  return matches;
}

This code searches for all occurrences of pattern in text using naive character-by-character matching.

Execution Table

Step	Operation	Text Index i	Pattern Index j	Match Check	Action	Match Found Positions
1	Start outer loop	0	-	-	Compare pattern at text[0]	[]
2	Compare chars	0	0	text[0] == pattern[0] ('a'=='a')	Continue	[]
3	Compare chars	0	1	text[1] == pattern[1] ('b'=='b')	Continue	[]
4	Compare chars	0	2	text[2] == pattern[2] ('c'=='c')	Continue	[]
5	Compare chars	0	3	text[3] == pattern[3] ('d'=='d')	Continue	[]
6	Compare chars	0	4	text[4] == pattern[4] ('a'=='a')	Continue	[]
7	Compare chars	0	5	text[5] == pattern[5] ('b'=='b')	Continue	[]
8	Compare chars	0	6	text[6] == pattern[6] ('c'=='c')	Continue	[]
9	Compare chars	0	7	text[7] == pattern[7] ('d'=='d')	Continue	[]
10	Compare chars	0	8	text[8] == pattern[8] ('a'=='a')	Continue	[]
11	Compare chars	0	9	text[9] == pattern[9] ('b'=='b')	Continue	[]
12	Compare chars	0	10	text[10] == pattern[10] ('c'=='c')	Continue	[]
13	Compare chars	0	11	text[11] == pattern[11] ('d'=='d')	Continue	[]
14	Pattern fully matched	0	12	j == pattern.length (12)	Record match at i=0	[0]
15	Increment i	1	-	-	Compare pattern at text[1]	[0]
16	Compare chars	1	0	text[1] == pattern[0] ('b'=='a')	Mismatch	[0]
17	Increment i	2	-	-	Compare pattern at text[2]	[0]
18	Compare chars	2	0	text[2] == pattern[0] ('c'=='a')	Mismatch	[0]
19	Increment i	3	-	-	Compare pattern at text[3]	[0]
20	Compare chars	3	0	text[3] == pattern[0] ('d'=='a')	Mismatch	[0]
21	Increment i	4	-	-	Compare pattern at text[4]	[0]
22	Compare chars	4	0	text[4] == pattern[0] ('a'=='a')	Continue	[0]
23	Compare chars	4	1	text[5] == pattern[1] ('b'=='b')	Continue	[0]
24	Compare chars	4	2	text[6] == pattern[2] ('c'=='c')	Continue	[0]
25	Compare chars	4	3	text[7] == pattern[3] ('d'=='d')	Continue	[0]
26	Compare chars	4	4	text[8] == pattern[4] ('a'=='a')	Continue	[0]
27	Compare chars	4	5	text[9] == pattern[5] ('b'=='b')	Continue	[0]
28	Compare chars	4	6	text[10] == pattern[6] ('c'=='c')	Continue	[0]
29	Compare chars	4	7	text[11] == pattern[7] ('d'=='d')	Continue	[0]
30	Pattern fully matched	4	12	j == pattern.length (12)	Record match at i=4	[0,4]
31	Increment i	5	-	-	Compare pattern at text[5]	[0,4]
32	Compare chars	5	0	text[5] == pattern[0] ('b'=='a')	Mismatch	[0,4]
33	Increment i	6	-	-	Compare pattern at text[6]	[0,4]
34	Compare chars	6	0	text[6] == pattern[0] ('c'=='a')	Mismatch	[0,4]
35	Increment i	7	-	-	Compare pattern at text[7]	[0,4]
36	Compare chars	7	0	text[7] == pattern[0] ('d'=='a')	Mismatch	[0,4]
37	Increment i	8	-	-	Compare pattern at text[8]	[0,4]
38	Compare chars	8	0	text[8] == pattern[0] ('a'=='a')	Continue	[0,4]
39	Compare chars	8	1	text[9] == pattern[1] ('b'=='b')	Continue	[0,4]
40	Compare chars	8	2	text[10] == pattern[2] ('c'=='c')	Continue	[0,4]
41	Compare chars	8	3	text[11] == pattern[3] ('d'=='d')	Continue	[0,4]
42	Pattern fully matched	8	12	j == pattern.length (12)	Record match at i=8	[0,4,8]
43	Increment i	9	-	-	Compare pattern at text[9]	[0,4,8]
44	Check loop condition	9	-	9 <= 20 - 12 (8)?	False	[0,4,8]

💡 i reached 9 which is greater than text length - pattern length, so loop ends

Variable Tracker

Variable	Start	After Step 14	After Step 30	After Step 42	Final
i	0	0	4	8	9 (loop ends)
j	-	12 (pattern matched)	12 (pattern matched)	12 (pattern matched)	-
Match Found Positions	[]	[0]	[0,4]	[0,4,8]	[0,4,8]

Key Moments - 3 Insights

Why do we stop comparing characters as soon as one mismatch is found?

Because the pattern cannot match if any character differs. The execution_table rows 16, 18, 20 show immediate mismatch stops to save time.

Why does the outer loop run only until i <= text.length - pattern.length?

Because if i is greater, the pattern would not fit in the remaining text. See execution_table row 44 where loop ends due to this condition.

Why do we increment i by 1 each time instead of skipping more?

Naive search checks every position for possible match. It does not skip ahead. This is shown in variable_tracker where i increments by 1 each time.

Visual Quiz - 3 Questions

Look at the execution_table at step 14, what does the algorithm record?

A A mismatch at text index 0

B Increment i to 1

C A match found starting at text index 0

D Pattern length is less than text length

💡 Hint

Check the 'Action' and 'Match Found Positions' columns at step 14

At which step does the outer loop condition become false and stop the search?

A Step 42

B Step 44

C Step 30

D Step 16

💡 Hint

Look at the 'Check loop condition' operation and the exit_note

If the pattern was shorter, how would the number of outer loop iterations change?

A More iterations because pattern fits more times

B Fewer iterations because pattern fits less times

C No change in iterations

D Outer loop would not run

💡 Hint

Refer to variable_tracker 'i' max value depends on text.length - pattern.length

Concept Snapshot

Naive String Pattern Matching:
- Start at text index i=0
- Compare pattern chars one by one
- If all match, record i
- Increment i by 1
- Stop when pattern can't fit
- Simple but slow for large texts

Full Transcript

The naive string pattern matching algorithm checks every possible position in the text where the pattern could fit. It compares each character of the pattern with the corresponding character in the text. If all characters match, it records the starting index. If a mismatch occurs, it moves to the next position in the text and repeats. The process stops when the pattern cannot fit in the remaining text. This method is straightforward but can be slow for large inputs.

Practice

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

easy

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

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

C. It sorts the text before searching for 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 every position in the text.

2. Step 2: Compare with other methods

   Other methods like hashing or trees are not part of the naive approach.

3. Final Answer:

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

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 naive sorts the text
• Assuming naive uses data structures like trees

2. Which of the following is the correct syntax to start a loop for naive pattern matching in JavaScript?
for (___; i <= text.length - pattern.length; i++)

easy

A. const i = 0

B. var i = 1

C. let i = 0

D. i = 0

Solution

1. Step 1: Identify loop initialization

   The loop variable must start at 0 to check from the beginning of the text.

2. Step 2: Choose correct declaration

   Using 'let' is correct for block scope and allows incrementing i.

3. Final Answer:

   let i = 0 -> Option C

4. Quick Check:

   Loop start = let i = 0 [OK]

Hint: Use 'let' to declare loop variable starting at zero [OK]

Common Mistakes:

• Using 'const' which cannot be incremented
• Starting loop at 1 instead of 0
• Not declaring variable with let or var

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

function naiveSearch(text, pattern) {
  let count = 0;
  for (let i = 0; i <= text.length - pattern.length; i++) {
    let j;
    for (j = 0; j < pattern.length; j++) {
      if (text[i + j] !== pattern[j]) break;
    }
    if (j === pattern.length) count++;
  }
  return count;
}

console.log(naiveSearch('abababa', 'aba'));

medium

A. 3

B. 2

C. 1

D. 0

Solution

1. Step 1: Check all pattern matches in text

   Positions checked: 0,1,2,3,4. Matches at 0 ('aba'), 2 ('aba'), and 4 ('aba').

2. Step 2: Count total matches

   There are 3 matches of 'aba' in 'abababa'.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Count matches = 3 [OK]

Hint: Count overlapping matches carefully [OK]

Common Mistakes:

• Missing overlapping matches
• Counting only non-overlapping occurrences
• Off-by-one errors in loop limits

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

function search(text, pattern) {
  for (let i = 0; i < text.length; i++) {
    let j = 0;
    while (j < pattern.length && text[i + j] === pattern[j]) {
      j++;
    }
    if (j === pattern.length) return i;
  }
  return -1;
}

medium

A. j should be declared with var instead of let

B. Loop condition should be i <= text.length - pattern.length

C. Return -1 should be inside the for loop

D. While loop condition should use || instead of &&

Solution

1. Step 1: Analyze loop range

   The outer loop runs till i < text.length, which can cause out-of-bound access when i + j exceeds text length.

2. Step 2: Correct loop condition

   It should be i <= text.length - pattern.length to avoid overflow.

3. Final Answer:

   Loop condition should be i <= text.length - pattern.length -> Option B

4. Quick Check:

   Loop limit fix = i <= text.length - pattern.length [OK]

Hint: Limit loop to avoid index overflow [OK]

Common Mistakes:

• Ignoring index overflow causing runtime errors
• Misplacing return statements
• Wrong logical operators in conditions

5. Given a text and a pattern, how can you modify the naive pattern matching algorithm to count only non-overlapping occurrences of the pattern in the text?

hard

A. Use recursion to find matches

B. Use a hash function to skip characters

C. Sort the text before searching

D. After finding a match, increment the outer loop index by pattern length instead of 1

Solution

1. Step 1: Understand overlapping vs non-overlapping

   Naive checks every position, counting overlapping matches. To avoid overlap, skip ahead after a match.

2. Step 2: Modify loop increment

   When a match is found, increase the index by pattern length to jump past the matched substring.

3. Final Answer:

   After finding a match, increment the outer loop index by pattern length instead of 1 -> Option D

4. Quick Check:

   Skip matched length to avoid overlap [OK]

Hint: Jump by pattern length after match to avoid overlaps [OK]

Common Mistakes:

• Trying to sort text which doesn't help
• Using hashing which is unrelated here
• Recursion adds complexity without solving overlap