String Pattern Matching Naive in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Naive Pattern Matching with Overlapping Matches

What is the output of the following C# code that uses naive string pattern matching to find all occurrences of a pattern in a text, including overlapping matches?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static List<int> NaivePatternMatch(string text, string pattern) {
        List<int> positions = new List<int>();
        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;
            }
            if (j == m) {
                positions.Add(i);
            }
        }
        return positions;
    }

    static void Main() {
        string text = "ababa";
        string pattern = "aba";
        var result = NaivePatternMatch(text, pattern);
        Console.WriteLine(string.Join(",", result));
    }
}

A "0"

B "0,1"

C "1,2"

D "0,2"

💡 Hint

Check how the inner loop compares characters and how overlapping matches are handled.

The naive pattern matching checks every position in the text where the pattern can fit. For text "ababa" and pattern "aba", matches occur at index 0 ("aba") and index 2 ("aba"), including overlapping occurrences.

❓ Predict Output

intermediate

Result of Naive Pattern Matching with No Matches

What does the following C# code print when the pattern does not appear in the text?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static List<int> NaivePatternMatch(string text, string pattern) {
        List<int> positions = new List<int>();
        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;
            }
            if (j == m) {
                positions.Add(i);
            }
        }
        return positions;
    }

    static void Main() {
        string text = "hello world";
        string pattern = "bye";
        var result = NaivePatternMatch(text, pattern);
        Console.WriteLine(string.Join(",", result));
    }
}

A ""

B "-1"

C "0"

D "null"

💡 Hint

Consider what the list contains if no matches are found.

If the pattern is not found, the positions list remains empty. Joining an empty list with commas results in an empty string.

🧠 Conceptual

advanced

Time Complexity of Naive Pattern Matching

What is the worst-case time complexity of the naive string pattern matching algorithm when searching for a pattern of length m in a text of length n?

A O(n * m)

B O(n + m)

C O(n^2)

D O(m^2)

💡 Hint

Consider the nested loops: one over the text and one over the pattern.

The naive algorithm checks each position in the text (n positions) and for each position compares up to m characters, resulting in O(n * m) time complexity.

🔧 Debug

advanced

Identify the Bug in Naive Pattern Matching Code

What issue will occur when running the following naive pattern matching code and why?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static List<int> NaivePatternMatch(string text, string pattern) {
        List<int> positions = new List<int>();
        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;
            }
            if (j == m) {
                positions.Add(i);
            }
        }
        return positions;
    }

    static void Main() {
        string text = "abcde";
        string pattern = "de";
        var result = NaivePatternMatch(text, pattern);
        Console.WriteLine(string.Join(",", result));
    }
}

A NullReferenceException due to uninitialized list

B No error, outputs "3"

C Misses the match at index 3 because loop condition misses last valid index

D Compilation error due to missing semicolon

💡 Hint

Check the loop boundary condition for the outer loop.

The outer loop runs with condition i < n - m, which excludes the last valid start index i=3 where the pattern "de" matches text[3:5]. The code outputs empty string instead of "3".

🚀 Application

expert

Number of Matches Found by Naive Pattern Matching

Given the text "aaaaa" and pattern "aa", how many matches will the naive pattern matching algorithm find?

A 2

B 4

C 3

D 5

💡 Hint

Consider overlapping matches carefully.

The pattern "aa" appears starting at indices 0, 1, 2, and 3 in the text "aaaaa". So there are 4 matches including overlaps.

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