String Pattern Matching Naive in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Naive Pattern Matching Function

What is the output of the following TypeScript code that uses a naive pattern matching approach to find all occurrences of a pattern in a text?

DSA Typescript

function naivePatternMatch(text: string, pattern: string): number[] {
  const result: number[] = [];
  const n = text.length;
  const m = pattern.length;
  for (let i = 0; i <= n - m; i++) {
    let j = 0;
    while (j < m && text[i + j] === pattern[j]) {
      j++;
    }
    if (j === m) {
      result.push(i);
    }
  }
  return result;
}

console.log(naivePatternMatch("abracadabra", "abra"));

A [0]

B [0, 7]

C [7]

D []

💡 Hint

Check all starting positions where the pattern matches fully in the text.

The pattern "abra" appears twice in the text "abracadabra". Once starting at index 0 and again starting at index 7.

🧠 Conceptual

intermediate

Number of Comparisons in Naive Pattern Matching

If the text length is 5 and the pattern length is 3, how many character comparisons does the naive pattern matching algorithm perform in the worst case?

A 12

B 15

C 9

D 8

💡 Hint

Worst case comparisons = (n - m + 1) * m

The naive algorithm compares the pattern at each possible position in the text. For text length n=5 and pattern length m=3, it tries (5 - 3 + 1) = 3 positions, each with up to 3 comparisons, totaling 9 comparisons.

🔧 Debug

advanced

Identify the Bug in Naive Pattern Matching Code

What error will the following TypeScript code produce when run, and why?

DSA Typescript

function naiveMatch(text: string, pattern: string): number[] {
  const result: number[] = [];
  const n = text.length;
  const m = pattern.length;
  for (let i = 0; i < n - m; i++) {
    let j = 0;
    while (j < m && text[i + j] === pattern[j]) {
      j++;
    }
    if (j === m) {
      result.push(i);
    }
  }
  return result;
}

console.log(naiveMatch("hellohello", "hello"));

A Returns [0]

B Returns []

C Runtime error: Index out of range

D Returns [0, 5]

💡 Hint

Check the loop boundary condition in the for loop.

The for loop uses i < n - m instead of i <= n - m. This causes it to miss checking the last valid position where the pattern could match, so it only finds the first occurrence.

❓ Predict Output

advanced

Output of Naive Pattern Matching with Overlapping Patterns

What is the output of this TypeScript code that finds all occurrences of pattern "aa" in the text "aaaa" using naive pattern matching?

DSA Typescript

function naivePatternMatch(text: string, pattern: string): number[] {
  const result: number[] = [];
  const n = text.length;
  const m = pattern.length;
  for (let i = 0; i <= n - m; i++) {
    let j = 0;
    while (j < m && text[i + j] === pattern[j]) {
      j++;
    }
    if (j === m) {
      result.push(i);
    }
  }
  return result;
}

console.log(naivePatternMatch("aaaa", "aa"));

A [0, 1]

B [0, 2]

C [1, 2]

D [0, 1, 2]

💡 Hint

Consider overlapping matches where the pattern starts at consecutive indices.

The pattern "aa" appears starting at indices 0, 1, and 2 in the text "aaaa" because matches can overlap.

🧠 Conceptual

expert

Time Complexity of Naive Pattern Matching in Worst Case

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

A O(n * m)

B O(n^2)

C O(n + m)

D O(m^2)

💡 Hint

Consider how many times characters are compared in the worst case.

The naive algorithm compares the pattern at each position in the text, and each comparison can take up to m steps, resulting in O(n * m) time complexity.

Practice

1. What does the naive string pattern matching algorithm do?

easy

A. It sorts the text before searching for the pattern.

B. It uses a hash function to find the pattern quickly.

C. It checks every possible position in the text to find the pattern.

D. It uses a tree structure to match the pattern.

Solution

1. Step 1: Understand naive pattern matching

   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

   Unlike hashing or trees, naive does not use extra data structures or preprocessing.

3. Final Answer:

   It checks every possible position in the text to find the pattern. -> Option C

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 advanced algorithms
• Thinking it sorts text before matching
• Assuming it uses trees or graphs

2. Which of the following is the correct syntax to start a loop from 0 to text.length - pattern.length in TypeScript for naive pattern matching?

easy

A. for (let i = 0; i < pattern.length; i++)

B. for (let i = 1; i < text.length - pattern.length; i++)

C. for (let i = 0; i < text.length; i++)

D. for (let i = 0; i <= text.length - pattern.length; i++)

Solution

1. Step 1: Determine loop range for matching

   The loop must start at 0 and go up to text.length - pattern.length inclusive to check all valid positions.

2. Step 2: Check syntax correctness

   for (let i = 0; i <= text.length - pattern.length; i++) uses <= and correct boundaries, others either start at 1 or wrong limits.

3. Final Answer:

   for (let i = 0; i <= text.length - pattern.length; i++) -> Option D

4. Quick Check:

   Loop from 0 to text.length - pattern.length inclusive [OK]

Hint: Loop till text length minus pattern length inclusive [OK]

Common Mistakes:

• Starting loop at 1 instead of 0
• Looping beyond valid range causing errors
• Using pattern length as loop limit

3. What will be the output of the following TypeScript code?

const text = "abcabcabc";
const pattern = "abc";
let count = 0;
for (let i = 0; i <= text.length - pattern.length; i++) {
  let j = 0;
  while (j < pattern.length && text[i + j] === pattern[j]) {
    j++;
  }
  if (j === pattern.length) {
    count++;
  }
}
console.log(count);

medium

A. 3

B. 2

C. 1

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

   The code increments count each time the pattern matches fully, so count becomes 3.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Pattern "abc" occurs 3 times [OK]

Hint: Count matches by checking each position fully [OK]

Common Mistakes:

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

4. Find the error in this naive pattern matching code snippet:

const text = "hellohello";
const pattern = "lo";
for (let i = 0; i < text.length - pattern.length; i++) {
  let j = 0;
  while (j < pattern.length && text[i + j] === pattern[j]) {
    j++;
  }
  if (j === pattern.length) {
    console.log(i);
  }
}

medium

A. The while condition should use || instead of &&.

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

C. The pattern length is incorrect.

D. The console.log should be outside the loop.

Solution

1. Step 1: Check loop boundary for matching

   The loop ends at text.length - pattern.length - 1 due to < operator, missing last valid position.

2. Step 2: Correct loop condition

   Changing < to <= includes the last position where pattern can match.

3. Final Answer:

   The loop should use <= instead of < to include last position. -> Option B

4. Quick Check:

   Loop boundary must cover all valid start indices [OK]

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

Common Mistakes:

• Using < instead of <= in loop
• Changing && to || in while condition
• Misplacing console.log outside loop

5. Given a text and a pattern, how can you modify the naive string pattern matching algorithm to count overlapping occurrences of the pattern in the text? For example, text = "aaaaa" and pattern = "aaa" should return 3.

hard

A. After finding a match, move the start index by 1 instead of pattern length.

B. After finding a match, move the start index by pattern length.

C. Use a hash function to detect overlaps.

D. Skip checking overlapping positions to improve speed.

Solution

1. Step 1: Understand overlapping matches

   Overlapping means matches can start inside a previous match, so we must check every position.

2. Step 2: Adjust index increment after match

   Instead of jumping by pattern length, increment start index by 1 to check next position for overlaps.

3. Final Answer:

   After finding a match, move the start index by 1 instead of pattern length. -> Option A

4. Quick Check:

   Increment by 1 to count overlaps [OK]

Hint: Move start by 1 after match to count overlaps [OK]

Common Mistakes:

• Skipping positions after match causing missed overlaps
• Using hash functions unnecessarily
• Trying to skip overlaps to speed up