String Pattern Matching Naive in DSA Go - 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

↓

Stop search

Start comparing the pattern at each position in the text until the pattern matches or the text ends.

Execution Sample

DSA Go

text := "abcxabcdabxabcdabcdabcy"
pattern := "abcdabcy"
for i := 0; i <= len(text)-len(pattern); i++ {
  match := true
  for j := 0; j < len(pattern); j++ {
    if text[i+j] != pattern[j] { match = false; break }
  }
  if match { fmt.Println("Pattern found at index", i) }
}

This code checks each position in the text to see if the pattern matches starting there.

Execution Table

Step	Operation	Text Index i	Pattern Index j	Character Compare	Match So Far	Action	Output
1	Start outer loop	0	-	-	true	Start comparing pattern at i=0	-
2	Compare chars	0	0	'a' == 'a'	true	Continue	-
3	Compare chars	0	1	'b' == 'b'	true	Continue	-
4	Compare chars	0	2	'c' == 'c'	true	Continue	-
5	Compare chars	0	3	'x' == 'd'	false	Mismatch, break inner loop	-
6	Increment i	1	-	-	-	Try next position i=1	-
7	Start outer loop	1	-	-	true	Start comparing pattern at i=1	-
8	Compare chars	1	0	'b' == 'a'	false	Mismatch, break inner loop	-
9	Increment i	2	-	-	-	Try next position i=2	-
10	Start outer loop	2	-	-	true	Start comparing pattern at i=2	-
11	Compare chars	2	0	'c' == 'a'	false	Mismatch, break inner loop	-
12	Increment i	3	-	-	-	Try next position i=3	-
13	Start outer loop	3	-	-	true	Start comparing pattern at i=3	-
14	Compare chars	3	0	'x' == 'a'	false	Mismatch, break inner loop	-
15	Increment i	4	-	-	-	Try next position i=4	-
16	Start outer loop	4	-	-	true	Start comparing pattern at i=4	-
17	Compare chars	4	0	'a' == 'a'	true	Continue	-
18	Compare chars	4	1	'b' == 'b'	true	Continue	-
19	Compare chars	4	2	'c' == 'c'	true	Continue	-
20	Compare chars	4	3	'd' == 'd'	true	Continue	-
21	Compare chars	4	4	'a' == 'a'	true	Continue	-
22	Compare chars	4	5	'b' == 'b'	true	Continue	-
23	Compare chars	4	6	'x' == 'c'	false	Mismatch, break inner loop	-
24	Increment i	5	-	-	-	Try next position i=5	-
25	Start outer loop	5	-	-	true	Start comparing pattern at i=5	-
26	Compare chars	5	0	'b' == 'a'	false	Mismatch, break inner loop	-
27	Increment i	6	-	-	-	Try next position i=6	-
28	Start outer loop	6	-	-	true	Start comparing pattern at i=6	-
29	Compare chars	6	0	'c' == 'a'	false	Mismatch, break inner loop	-
30	Increment i	7	-	-	-	Try next position i=7	-
31	Start outer loop	7	-	-	true	Start comparing pattern at i=7	-
32	Compare chars	7	0	'd' == 'a'	false	Mismatch, break inner loop	-
33	Increment i	8	-	-	-	Try next position i=8	-
34	Start outer loop	8	-	-	true	Start comparing pattern at i=8	-
35	Compare chars	8	0	'a' == 'a'	true	Continue	-
36	Compare chars	8	1	'b' == 'b'	true	Continue	-
37	Compare chars	8	2	'x' == 'c'	false	Mismatch, break inner loop	-
38	Increment i	9	-	-	-	Try next position i=9	-
39	Start outer loop	9	-	-	true	Start comparing pattern at i=9	-
40	Compare chars	9	0	'b' == 'a'	false	Mismatch, break inner loop	-
41	Increment i	10	-	-	-	Try next position i=10	-
42	Start outer loop	10	-	-	true	Start comparing pattern at i=10	-
43	Compare chars	10	0	'x' == 'a'	false	Mismatch, break inner loop	-
44	Increment i	11	-	-	-	Try next position i=11	-
45	Start outer loop	11	-	-	true	Start comparing pattern at i=11	-
46	Compare chars	11	0	'a' == 'a'	true	Continue	-
47	Compare chars	11	1	'b' == 'b'	true	Continue	-
48	Compare chars	11	2	'c' == 'c'	true	Continue	-
49	Compare chars	11	3	'd' == 'd'	true	Continue	-
50	Compare chars	11	4	'a' == 'a'	true	Continue	-
51	Compare chars	11	5	'b' == 'b'	true	Continue	-
52	Compare chars	11	6	'c' == 'c'	true	Continue	-
53	Compare chars	11	7	'y' == 'y'	true	Pattern matched fully	Pattern found at index 11
54	Increment i	12	-	-	-	Try next position i=12	-
55	Start outer loop	12	-	-	true	Start comparing pattern at i=12	-
56	Compare chars	12	0	'b' == 'a'	false	Mismatch, break inner loop	-
57	Increment i	13	-	-	-	Try next position i=13	-
58	Start outer loop	13	-	-	true	Start comparing pattern at i=13	-
59	Compare chars	13	0	'c' == 'a'	false	Mismatch, break inner loop	-
60	Increment i	14	-	-	-	Try next position i=14	-
61	Start outer loop	14	-	-	true	Start comparing pattern at i=14	-
62	Compare chars	14	0	'd' == 'a'	false	Mismatch, break inner loop	-
63	Increment i	15	-	-	-	Try next position i=15	-
64	Start outer loop	15	-	-	true	Start comparing pattern at i=15	-
65	Compare chars	15	0	'a' == 'a'	true	Continue	-
66	Compare chars	15	1	'b' == 'b'	true	Continue	-
67	Compare chars	15	2	'c' == 'c'	true	Continue	-
68	Compare chars	15	3	'd' == 'd'	true	Continue	-
69	Compare chars	15	4	'a' == 'a'	true	Continue	-
70	Compare chars	15	5	'b' == 'b'	true	Continue	-
71	Compare chars	15	6	'c' == 'c'	true	Continue	-
72	Compare chars	15	7	'y' == 'y'	true	Pattern matched fully	Pattern found at index 15
73	Increment i	16	-	-	-	Try next position i=16	-
74	Check loop condition	16	-	-	-	i > len(text)-len(pattern), stop	-

💡 i reaches 16, condition 16 <= 24-8 is False, search ends

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	After 8	After 9	After 10	After 11	After 12	After 13	After 14	After 15	After 16	Final
i	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	16
j	-	3	1	1	0	0	0	0	2	0	0	7	0	0	0	7	-	-
match	true	false	false	false	true	false	false	false	false	false	false	true	false	false	false	true	-	-

Key Moments - 3 Insights

Why does the inner loop break early when a mismatch is found?

Because once a character doesn't match, continuing to check the rest of the pattern is pointless. This is shown in execution_table rows like 5 and 23 where 'match' becomes false and the inner loop breaks.

Why does the outer loop stop when i > len(text) - len(pattern)?

Because starting the pattern beyond that point means the pattern would not fit entirely in the remaining text. This is shown in the exit_note and row 74 where the loop condition fails.

What does 'match' variable represent during execution?

'match' tracks if all characters matched so far at the current position i. If any mismatch occurs, it becomes false and the inner loop breaks, as seen in variable_tracker and execution_table rows.

Visual Quiz - 3 Questions

Look at the execution_table at step 23. What is the value of 'match' after comparing text[4+6] and pattern[6]?

A true

B false

C undefined

D true but breaks anyway

💡 Hint

Check the 'Match So Far' column at step 23 in execution_table.

At which value of i does the pattern first fully match the text?

A 11

B 4

C 15

D 0

💡 Hint

Look for 'Pattern found at index' output in execution_table rows.

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

A Fewer iterations

B No change

C More iterations

D Infinite loop

💡 Hint

Refer to the exit condition i <= len(text) - len(pattern) in concept_flow and exit_note.

Concept Snapshot

Naive String Pattern Matching:
- Check pattern at each text index i
- Compare characters one by one
- If mismatch, move to next i
- Stop when i > text length - pattern length
- Prints all match positions

Full Transcript

This visualization shows how the naive string pattern matching algorithm works by checking each position in the text to see if the pattern matches starting there. The outer loop moves the starting index i from 0 up to the point where the pattern can still fit. The inner loop compares each character of the pattern with the corresponding character in the text. If any character mismatches, the inner loop breaks early and the outer loop increments i to try the next position. When all characters match, the pattern is found and the index is printed. The process continues until no more positions remain to check. Variables i, j, and match track the current indices and matching status. The execution table shows each comparison step, the match status, and actions taken. Key moments clarify why the inner loop breaks early, why the outer loop stops at a certain point, and what the match variable means. The quiz tests understanding of match status, first match position, and effect of pattern length on iterations.

Practice

1. What is the main idea behind the naive string pattern matching algorithm?

easy

A. Check every possible position in the text for the pattern

B. Use a hash function to find the pattern quickly

C. Preprocess the pattern to skip some comparisons

D. Sort the text and pattern before matching

Solution

1. Step 1: Understand naive matching approach

   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

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

3. Final Answer:

   Check every possible position in the text for the pattern -> Option A

4. Quick Check:

   Naive = Check all positions [OK]

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

Common Mistakes:

• Thinking naive uses hashing
• Assuming pattern preprocessing is done
• Believing text is sorted first

2. Which of the following Go code snippets correctly starts the outer loop for naive string pattern matching?

easy

A. for i := 0; i <= len(text)-len(pattern); i++ {

B. for i := 0; i < len(text); i++ {

C. for i := 1; i <= len(text); i++ {

D. for i := 0; i < len(pattern); i++ {

Solution

1. Step 1: Determine loop range for matching

   The outer loop must run from 0 to len(text)-len(pattern) to avoid out-of-range errors.

2. Step 2: Check each option

   for i := 0; i <= len(text)-len(pattern); i++ { correctly uses i <= len(text)-len(pattern). Others either go too far or use wrong limits.

3. Final Answer:

   for i := 0; i <= len(text)-len(pattern); i++ { -> Option A

4. Quick Check:

   Loop till text length minus pattern length [OK]

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

Common Mistakes:

• Looping beyond valid start positions
• Starting loop from 1 instead of 0
• Using pattern length as loop limit

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

text := "banana"
pattern := "ana"
count := 0
for i := 0; i <= len(text)-len(pattern); i++ {
  j := 0
  for j < len(pattern) && text[i+j] == pattern[j] {
    j++
  }
  if j == len(pattern) {
    count++
  }
}
fmt.Println(count)

medium

A. 1

B. 3

C. 0

D. 2

Solution

1. Step 1: Identify pattern matches in text

   Check each position in "banana" for "ana": positions 1-3 and 3-5 match.

2. Step 2: Count matches

   Two matches found, so count is 2.

3. Final Answer:

   2 -> Option D

4. Quick Check:

   "ana" appears twice in "banana" [OK]

Hint: Count all exact matches sliding over text [OK]

Common Mistakes:

• Counting overlapping matches incorrectly
• Off-by-one errors in loop limits
• Assuming only first match counts

4. The following Go code tries to count pattern occurrences but has a bug. What is the bug?

text := "abcabcabc"
pattern := "abc"
count := 0
for i := 0; i < len(text)-len(pattern); i++ {
  j := 0
  for j < len(pattern) && text[i+j] == pattern[j] {
    j++
  }
  if j == len(pattern) {
    count++
  }
}
fmt.Println(count)

medium

A. The inner loop condition is wrong

B. The outer loop should use <= instead of <

C. The count variable is not initialized

D. The pattern length is not checked

Solution

1. Step 1: Analyze outer loop range

   The loop runs from 0 to len(text)-len(pattern)-1, missing last valid start index.

2. Step 2: Correct loop condition

   Changing < to <= includes last position, fixing missed matches.

3. Final Answer:

   The outer loop should use <= instead of < -> Option B

4. Quick Check:

   Loop must cover last valid start index [OK]

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

Common Mistakes:

• Using < instead of <= in outer loop
• Ignoring last possible match position
• Misunderstanding loop boundaries

5. Given the text "abracadabra" and pattern "abra", how many times will the naive algorithm find the pattern if overlapping matches are counted? Use the naive approach code below:

text := "abracadabra"
pattern := "abra"
count := 0
for i := 0; i <= len(text)-len(pattern); i++ {
  j := 0
  for j < len(pattern) && text[i+j] == pattern[j] {
    j++
  }
  if j == len(pattern) {
    count++
  }
}
fmt.Println(count)

hard

A. 3

B. 1

C. 2

D. 4

Solution

1. Step 1: Identify all pattern matches including overlaps

   "abra" appears at positions 0-3 and 7-10 in "abracadabra".

2. Step 2: Count total matches

   Two matches found, so count is 2.

3. Final Answer:

   2 -> Option C

4. Quick Check:

   "abra" occurs twice overlapping allowed [OK]

Hint: Check all positions including overlaps [OK]

Common Mistakes:

• Counting only first match
• Missing second overlapping match
• Confusing substring positions