String Pattern Matching Naive in DSA C - Execution Trace

Concept Flow - String Pattern Matching Naive

Start at text index i=0

↓

Check if pattern matches at i

↓

Record match

↓

Is i <= text length - pattern length?

Yes↓

Repeat

No↓

End

Start checking from each position in the text if the pattern matches fully. If yes, record match. Always move to next position. Repeat until no more positions to check.

Execution Sample

DSA C

text = "ABABAB"
pattern = "ABA"
for i in 0 to len(text)-len(pattern):
  check if text[i..i+len(pattern)-1] == pattern
  if yes, print i

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

Execution Table

Step	Operation	Text Index i	Pattern Index j	Match So Far	Action	Matches Found	Visual State
1	Start checking at i=0	0	-	None	Check pattern at i=0	[]	Text: ABABAB Pattern: ABA Checking at i=0
2	Compare text[0] and pattern[0]	0	0	A == A	Continue	[]	A vs A: match
3	Compare text[1] and pattern[1]	0	1	B == B	Continue	[]	B vs B: match
4	Compare text[2] and pattern[2]	0	2	A == A	Full match	[]	A vs A: match
5	Pattern matched at i=0	0	2	Full match	Record match	[0]	Match at index 0
6	Increment i to 1	1	-	None	Check pattern at i=1	[0]	Checking at i=1
7	Compare text[1] and pattern[0]	1	0	B != A	Mismatch	[0]	B vs A: no match
8	Increment i to 2	2	-	None	Check pattern at i=2	[0]	Checking at i=2
9	Compare text[2] and pattern[0]	2	0	A == A	Continue	[0]	A vs A: match
10	Compare text[3] and pattern[1]	2	1	B == B	Continue	[0]	B vs B: match
11	Compare text[4] and pattern[2]	2	2	A == A	Full match	[0]	A vs A: match
12	Pattern matched at i=2	2	2	Full match	Record match	[0, 2]	Match at index 2
13	Increment i to 3	3	-	None	Check pattern at i=3	[0, 2]	Checking at i=3
14	Compare text[3] and pattern[0]	3	0	B != A	Mismatch	[0, 2]	B vs A: no match
15	Increment i to 4	4	-	None	Check pattern at i=4	[0, 2]	Checking at i=4
16	Compare text[4] and pattern[0]	4	0	A == A	Continue	[0, 2]	A vs A: match
17	Compare text[5] and pattern[1]	4	1	B == B	Continue	[0, 2]	B vs B: match
18	Compare text[6] and pattern[2]	4	2	Index out of range	Stop	[0, 2]	No character at text[6]
19	End checking, no more positions	-	-	-	-	[0, 2]	Matches found at indices 0 and 2

💡 i reached 4 which is text length - pattern length, no further full pattern check possible

Variable Tracker

Variable	Start	After Step 5	After Step 12	Final
i	0	0	2	4
j	-	2	2	-
Matches Found	[]	[0]	[0, 2]	[0, 2]

Key Moments - 3 Insights

Why do we stop checking when i reaches text length - pattern length + 1?

Because starting beyond that point, the pattern would not fit fully in the text. See execution_table row 18 where index 6 is out of range.

Why do we compare characters one by one instead of the whole substring at once?

Because naive matching checks each character to confirm a full match. Partial mismatch stops early. See rows 2-4 and 9-11 for character comparisons.

What happens when a mismatch occurs during pattern check?

We stop checking at that position and move to the next index i. See row 7 and 14 where mismatch causes increment of i.

Visual Quiz - 3 Questions

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

A 1

B 2

C 0

D 3

💡 Hint

Check the 'Matches Found' column and find when the second match is recorded (row 12).

At which step does the first mismatch occur during pattern checking?

A Step 7

B Step 14

C Step 18

D Step 3

💡 Hint

Look for the first 'Mismatch' action in the 'Action' column in execution_table.

If the pattern was "BAB" instead of "ABA", how would the matches found change?

A No matches found

B Matches at indices 0 and 2

C Matches at indices 1 and 3

D Matches at indices 2 and 4

💡 Hint

Think about where "BAB" appears in "ABABAB" and relate to the 'Matches Found' variable_tracker.

Concept Snapshot

Naive String Pattern Matching:
- Check each text index i from 0 to (text length - pattern length)
- Compare pattern characters one by one with text starting at i
- If all match, record i as a match
- If mismatch, move to next i
- Stops when no more full pattern fits in text

Full Transcript

Naive string pattern matching checks every possible position in the text to see if the pattern appears starting there. It compares characters one by one. If all characters match, it records the position. If a mismatch occurs, it moves to the next position. The process stops when the remaining text is shorter than the pattern. This method is simple but can be slow for large texts and patterns.

Practice

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

easy

A. Check every possible position in the text to find 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 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 preprocessing
• Thinking naive skips some positions
• Assuming sorting is involved

2. Which of the following is the correct syntax to start a loop for naive pattern matching in C to check each position in the text of length n for a pattern of length m?

easy

A. for (int i = 0; i < n; i++)

B. for (int i = 0; i <= n - m; i++)

C. for (int i = 0; i < m; i++)

D. for (int i = 0; i <= n; i++)

Solution

1. Step 1: Determine loop range for pattern matching

   We must check positions where the pattern fits fully, so i goes from 0 to n - m inclusive.

2. Step 2: Check options

   for (int i = 0; i <= n - m; i++) correctly uses i <= n - m. Others either go beyond or do not cover all valid positions.

3. Final Answer:

   for (int i = 0; i <= n - m; i++) -> Option B

4. Quick Check:

   Loop till n - m inclusive [OK]

Hint: Loop till n - m to fit pattern fully [OK]

Common Mistakes:

• Looping till n instead of n - m
• Using < instead of <= causing missed checks
• Looping only till m

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

char text[] = "abcabcabc";
char pattern[] = "abc";
int n = 9, m = 3;
int count = 0;
for (int i = 0; i <= n - m; i++) {
    int j;
    for (j = 0; j < m; j++) {
        if (text[i + j] != pattern[j])
            break;
    }
    if (j == m) count++;
}
printf("%d\n", count);

medium

A. 1

B. 2

C. 0

D. 3

Solution

1. Step 1: Identify pattern matches in text

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

2. Step 2: Count matches

   Each match increments count, so total count is 3.

3. Final Answer:

   3 -> Option D

4. Quick Check:

   Pattern found 3 times [OK]

Hint: Count all exact matches by checking each position [OK]

Common Mistakes:

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

4. Identify the bug in the following naive pattern matching code snippet and choose the correct fix.

char text[] = "hellohello";
char pattern[] = "hello";
int n = 10, m = 5;
int count = 0;
for (int i = 0; i < n - m; i++) {
    int j;
    for (j = 0; j < m; j++) {
        if (text[i + j] != pattern[j])
            break;
    }
    if (j == m) count++;
}
printf("%d\n", count);

medium

A. Change loop condition to i <= n - m

B. Change inner loop to j <= m

C. Initialize count to 1

D. Use strcpy instead of comparison

Solution

1. Step 1: Analyze outer loop range

   The loop runs from i = 0 to i < n - m, which misses the last valid position at i = n - m.

2. Step 2: Fix loop condition

   Changing to i <= n - m ensures all valid positions are checked.

3. Final Answer:

   Change loop condition to i <= n - m -> Option A

4. Quick Check:

   Loop must include last valid index [OK]

Hint: Use <= n - m to include last valid start [OK]

Common Mistakes:

• Using < instead of <= in outer loop
• Changing inner loop incorrectly
• Misusing string functions for comparison

5. Given a text "abababab" and a pattern "aba", how many times will the naive pattern matching algorithm count the pattern occurrences including overlapping matches?

hard

A. 2

B. 5

C. 3

D. 4

Solution

1. Step 1: Identify all starting positions for pattern

   Text length n=8, pattern length m=3, so i from 0 to 5 inclusive.

2. Step 2: Check matches including overlaps

   Matches at positions 0 ("aba"), 2 ("aba"), and 4 ("aba") total 3 matches.

3. Final Answer:

   3 -> Option C

4. Quick Check:

   Count overlapping matches carefully [OK]

Hint: Check every position, count overlaps too [OK]

Common Mistakes:

• Ignoring overlapping matches
• Counting only non-overlapping occurrences
• Off-by-one errors in loop range