String Pattern Matching Naive in DSA C# - 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 from the beginning of the text and check if the pattern matches at each position until the end is reached.

Execution Sample

DSA C#

string text = "ABABABC";
string pattern = "ABABC";
for (int i = 0; i <= text.Length - pattern.Length; i++) {
  int j;
  for (j = 0; j < pattern.Length; j++) {
    if (text[i + j] != pattern[j]) break;
  }
  if (j == pattern.Length) Console.WriteLine(i);
}

This code checks each position in the text to see if the pattern matches starting there, printing the index if it does.

Execution Table

Step	Operation	Text Index i	Pattern Index j	Comparison	Match So Far	Action	Pattern Found Indices
1	Start outer loop	0	-	-	-	Check pattern at i=0	[]
2	Compare chars	0	0	text[0]='A' == pattern[0]='A'	Yes	Continue	[]
3	Compare chars	0	1	text[1]='B' == pattern[1]='B'	Yes	Continue	[]
4	Compare chars	0	2	text[2]='A' == pattern[2]='A'	Yes	Continue	[]
5	Compare chars	0	3	text[3]='B' == pattern[3]='B'	Yes	Continue	[]
6	Compare chars	0	4	text[4]='A' != pattern[4]='C'	No	Break inner loop	[]
7	Increment i	1	-	-	-	Check pattern at i=1	[]
8	Compare chars	1	0	text[1]='B' != pattern[0]='A'	No	Break inner loop	[]
9	Increment i	2	-	-	-	Check pattern at i=2	[]
10	Compare chars	2	0	text[2]='A' == pattern[0]='A'	Yes	Continue	[]
11	Compare chars	2	1	text[3]='B' == pattern[1]='B'	Yes	Continue	[]
12	Compare chars	2	2	text[4]='A' == pattern[2]='A'	Yes	Continue	[]
13	Compare chars	2	3	text[5]='B' == pattern[3]='B'	Yes	Continue	[]
14	Compare chars	2	4	text[6]='C' == pattern[4]='C'	Yes	Continue	[]
15	Pattern matched	2	5	-	Full match	Print index 2	[2]
16	Increment i	3	-	-	-	Check pattern at i=3	[2]
17	Compare chars	3	0	text[3]='B' != pattern[0]='A'	No	Break inner loop	[2]
18	Increment i	4	-	-	-	Check pattern at i=4	[2]
19	Compare chars	4	0	text[4]='A' == pattern[0]='A'	Yes	Continue	[2]
20	Compare chars	4	1	text[5]='B' == pattern[1]='B'	Yes	Continue	[2]
21	Compare chars	4	2	text[6]='C' != pattern[2]='A'	No	Break inner loop	[2]
22	Increment i	5	-	-	-	i > text.Length - pattern.Length, stop	[2]

💡 i reached 5 which is greater than text length - pattern length (7 - 5 = 2), so search ends.

Variable Tracker

Variable	Start	After Step 6	After Step 8	After Step 15	After Step 21	Final
i	0	0	1	2	4	5
j	-	4	0	5	2	-
Pattern Found Indices	[]	[]	[]	[2]	[2]	[2]

Key Moments - 3 Insights

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

Because as soon as one character does not match, the pattern cannot match at that position, so we stop checking further (see steps 6, 8, 21 in execution_table).

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

Because beyond that point, the remaining text is shorter than the pattern, so a full match is impossible (see step 22 in execution_table).

Why do we print the index only when j equals pattern length?

Because j counts matched characters; when it equals the pattern length, it means all characters matched successfully (see step 15 in execution_table).

Visual Quiz - 3 Questions

Look at the execution_table at step 6, what caused the inner loop to break?

A All characters matched perfectly

B Outer loop index i was incremented

C Characters at text[4] and pattern[4] did not match

D Pattern length was exceeded

💡 Hint

Check the 'Comparison' and 'Action' columns at step 6 in execution_table

At which step does the pattern fully match the text?

A Step 8

B Step 15

C Step 21

D Step 4

💡 Hint

Look for 'Pattern matched' and 'Print index' in execution_table

If the pattern was "ABA" instead of "ABABC", how would the final pattern found indices change?

A [0,2]

B [2]

C []

D [1,3]

💡 Hint

Consider how shorter pattern length affects matches and check variable_tracker for pattern found indices

Concept Snapshot

Naive String Pattern Matching:
- Check each text position i from 0 to text.Length - pattern.Length
- For each i, compare pattern chars one by one
- If all match, pattern found at i
- Stop when remaining text is shorter than pattern
- Simple but inefficient for large texts

Full Transcript

The naive string pattern matching algorithm checks every possible position in the text to see if the pattern matches starting there. It uses two loops: the outer loop moves the starting index i through the text, and the inner loop compares each character of the pattern with the corresponding character in the text. If a mismatch occurs, the inner loop breaks early and the outer loop moves to the next position. When all characters match, the index i is printed as a match. The search stops when the remaining text is shorter than the pattern length. This method is straightforward but can be slow for large inputs.

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. Build a prefix table to skip unnecessary 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 every position in the text.

2. Step 2: Compare with other methods

   Other methods like hashing or prefix tables are not used in naive matching.

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 prefix methods
• Thinking naive skips positions
• Assuming sorting is involved

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

easy

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

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

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

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

Solution

1. Step 1: Determine loop range for pattern matching

   The loop must run from 0 to n - m inclusive to avoid overflow when matching pattern of length m.

2. Step 2: Check each option

   for (int i = 0; i <= n - m; i++) correctly uses i <= n - m. Others either go beyond or are too short.

3. Final Answer:

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

4. Quick Check:

   Loop till n - m inclusive [OK]

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

Common Mistakes:

• Looping till n causes index out of range
• Looping till m is too short
• Using < instead of <= misses last position

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

string text = "abcabcabc";
string pattern = "abc";
int count = 0;
for (int i = 0; i <= text.Length - pattern.Length; i++) {
    int j;
    for (j = 0; j < pattern.Length; j++) {
        if (text[i + j] != pattern[j])
            break;
    }
    if (j == pattern.Length)
        count++;
}
Console.WriteLine(count);

medium

A. 1

B. 2

C. 3

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 in the loop

   The inner loop confirms full matches at these positions, so count increments 3 times.

3. Final Answer:

   3 -> Option C

4. Quick Check:

   Pattern occurs 3 times [OK]

Hint: Count full matches by checking all pattern chars [OK]

Common Mistakes:

• Counting partial matches
• Off-by-one errors in loop limits
• Breaking early without counting

4. The following code tries to implement naive pattern matching but does not work correctly. What is the bug?

string text = "hellohello";
string pattern = "lo";
int count = 0;
for (int i = 0; i < text.Length - pattern.Length; i++) {
    int j;
    for (j = 0; j < pattern.Length; j++) {
        if (text[i + j] != pattern[j])
            break;
    }
    if (j == pattern.Length)
        count++;
}
Console.WriteLine(count);

medium

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

B. The inner loop should start from 1 instead of 0

C. The pattern length is not used correctly

D. The count variable is not initialized

Solution

1. Step 1: Analyze loop boundary

   The outer loop runs from 0 to text.Length - pattern.Length - 1, missing the last valid start position.

2. Step 2: Correct loop condition

   Changing < to <= ensures the last possible position is checked for pattern match.

3. Final Answer:

   The outer loop should use <= instead of < to include last position -> Option A

4. Quick Check:

   Loop boundary off by one [OK]

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

Common Mistakes:

• Using < causes missing last match
• Changing inner loop start breaks matching
• Ignoring initialization of count

5. Given a text "ababababab" and a pattern "abab", how many times will the naive pattern matching algorithm find the pattern if overlapping matches are counted?

hard

A. 2

B. 4

C. 3

D. 5

Solution

1. Step 1: Identify all overlapping matches

   The pattern "abab" appears starting at indices 0, 2, 4, and 6 in the text "ababababab".

2. Step 2: Count total matches including overlaps

   Counting all these positions gives 4 matches.

3. Final Answer:

   4 -> Option B

4. Quick Check:

   Overlapping matches counted = 4 [OK]

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

Common Mistakes:

• Ignoring overlapping matches
• Counting only non-overlapping occurrences
• Miscounting start indices