String Pattern Matching Naive in DSA C# - Build from Scratch

String Pattern Matching Naive

📖 Scenario: Imagine you have a long text message and you want to find where a smaller word or pattern appears inside it. This is like looking for a friend's name in a long letter.

🎯 Goal: You will write a simple program that checks every possible place in the text to see if the pattern matches exactly. This is called the naive string pattern matching method.

📋 What You'll Learn

Create a string variable called text with the value "abracadabra".

Create a string variable called pattern with the value "abra".

Write a loop to check each position in text where pattern could start.

Inside the loop, check if the substring of text matches pattern exactly.

If a match is found, add the starting index to a list called matches.

Print the list matches showing all starting positions where pattern appears in text.

💡 Why This Matters

🌍 Real World

Finding patterns in text is useful in searching documents, DNA sequences, or logs.

💼 Career

Understanding string matching helps in roles like software development, data analysis, and cybersecurity.

1

Create the text and pattern strings

Create a string variable called text with the value "abracadabra" and a string variable called pattern with the value "abra".

DSA C#

// Create the text and pattern strings
// Your code here

Hint

Use string type and assign the exact values given.

2

Create a list to store match positions

Create a list of integers called matches to store the starting indexes where pattern matches text.

DSA C#

string text = "abracadabra";
string pattern = "abra";
// Create a list to store match positions
// Your code here

Hint

Use List<int> and initialize it with new List<int>().

3

Check each position in text for the pattern

Write a for loop with variable i from 0 to text.Length - pattern.Length. Inside it, write another for loop with variable j from 0 to pattern.Length to check if text[i + j] equals pattern[j]. If all characters match, add i to matches.

DSA C#

string text = "abracadabra";
string pattern = "abra";
List matches = new List();
// Write nested loops to check for pattern matches
// Your code here

Hint

Use two loops: outer loop for each possible start, inner loop to compare characters.

4

Print the list of match positions

Print the matches list using Console.WriteLine to show all starting indexes where pattern appears in text. Use string.Join to join the indexes with commas.

DSA C#

string text = "abracadabra";
string pattern = "abra";
List matches = new List();

for (int i = 0; i <= text.Length - pattern.Length; i++)
{
    bool found = true;
    for (int j = 0; j < pattern.Length; j++)
    {
        if (text[i + j] != pattern[j])
        {
            found = false;
            break;
        }
    }
    if (found)
    {
        matches.Add(i);
    }
}
// Print the matches list
// Your code here

Hint

Use Console.WriteLine(string.Join(",", matches)) to print the list as comma-separated values.

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