String Pattern Matching Naive in DSA C#

Mental Model

Check every possible place in the text to see if the pattern matches exactly.

Analogy: Like looking for a small picture in a big photo by sliding the small picture over every spot and comparing pixel by pixel.

Text:  T  E  X  T  T  E  X  T  T  E  X  T
         ↑
Pattern: P  A  T  T  E  R  N

Dry Run Walkthrough

Input: text: "ABABABC", pattern: "ABABC"

Goal: Find the starting index where the pattern "ABABC" appears in the text "ABABABC"

Step 1: Check text starting at index 0 for pattern match

Text: A B A B A B C
       ↑
Pattern: A B A B C
         ↑

Why: Start matching pattern from the beginning of the text

Step 2: Compare characters one by one: A==A, B==B, A==A, B==B, C==A (mismatch)

Mismatch at pattern index 4, text index 4
Text: A B A B A B C
         ↑
Pattern: A B A B C
             ↑

Why: Mismatch means pattern does not match here, move to next text index

Step 3: Check text starting at index 1 for pattern match

Text: A B A B A B C
         ↑
Pattern: A B A B C
         ↑

Why: Try matching pattern starting from next position in text

Step 4: Compare characters one by one: B==A (mismatch immediately)

Mismatch at pattern index 0, text index 1
Text: A B A B A B C
           ↑
Pattern: A B A B C
         ↑

Why: Mismatch at first character means move to next text index

Step 5: Check text starting at index 2 for pattern match

Text: A B A B A B C
           ↑
Pattern: A B A B C
         ↑

Why: Try matching pattern starting from index 2

Step 6: Compare characters one by one: A==A, B==B, A==A, B==B, C==C (all match)

Full pattern matched starting at index 2
Text: A B A B A B C
           ↑
Pattern: A B A B C
           ↑

Why: Pattern found at index 2

Result:

Pattern found at index 2

Annotated Code

DSA C#

using System;

class NaivePatternMatching
{
    public static int Search(string text, string pattern)
    {
        int n = text.Length;
        int m = pattern.Length;

        for (int i = 0; i <= n - m; i++)
        {
            int j;
            for (j = 0; j < m; j++)
            {
                if (text[i + j] != pattern[j])
                    break; // mismatch found, stop checking this position
            }
            if (j == m) // all characters matched
                return i; // pattern found at index i
        }
        return -1; // pattern not found
    }

    static void Main()
    {
        string text = "ABABABC";
        string pattern = "ABABC";
        int index = Search(text, pattern);
        if (index != -1)
            Console.WriteLine($"Pattern found at index {index}");
        else
            Console.WriteLine("Pattern not found");
    }
}

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

slide pattern start index over text from 0 to last possible start

for (j = 0; j < m; j++)

compare each character of pattern with text at current start

if (text[i + j] != pattern[j]) break;

stop checking this start if any character mismatches

if (j == m) return i;

if all characters matched, return current start index

Output

Pattern found at index 2

Complexity Analysis

Time: O(n*m) because for each of the n-m+1 positions in text, we compare up to m characters

Space: O(1) because no extra space is used except variables

vs Alternative: Naive is slower than advanced algorithms like KMP which run in O(n+m) by avoiding repeated comparisons

Edge Cases

Empty pattern

Returns 0 immediately since empty pattern matches at start

DSA C#

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

Pattern longer than text

No match possible, returns -1

DSA C#

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

Pattern equals text

Returns 0 since full match at start

DSA C#

if (j == m) return i;

When to Use This Pattern

When asked to find if a small string appears inside a bigger string and no advanced algorithm is required, use naive pattern matching by checking every possible position.

Common Mistakes

Mistake: Not stopping inner loop on mismatch and continuing to compare unnecessary characters
Fix: Add break statement immediately when a mismatch is found

Mistake: Looping beyond text length causing index out of range
Fix: Limit outer loop to n - m to avoid overflow

Summary

Checks every possible position in the text to find the pattern by comparing characters one by one.

Use when pattern matching is simple and input sizes are small or when learning the basics.

The key insight is sliding the pattern over the text and stopping early on mismatches to avoid unnecessary checks.

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