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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Naive Pattern Matching for Single Occurrence

What is the output of the following JavaScript code that uses naive string pattern matching to find the first occurrence of a pattern in a text?

DSA Javascript

function naiveSearch(text, pattern) {
  for (let i = 0; i <= text.length - pattern.length; i++) {
    let j;
    for (j = 0; j < pattern.length; j++) {
      if (text[i + j] !== pattern[j]) {
        break;
      }
    }
    if (j === pattern.length) {
      return i;
    }
  }
  return -1;
}

console.log(naiveSearch('abracadabra', 'cada'));

A 4

B -1

C 3

D 0

💡 Hint

Check where the substring 'cada' starts in 'abracadabra'.

The pattern 'cada' starts at index 3 in the text 'abracadabra'. The naive search returns the starting index of the first match.

❓ Predict Output

intermediate

Output when Pattern is Not Found

What will be the output of this naive pattern matching code when the pattern does not exist in the text?

DSA Javascript

function naiveSearch(text, pattern) {
  for (let i = 0; i <= text.length - pattern.length; i++) {
    let j;
    for (j = 0; j < pattern.length; j++) {
      if (text[i + j] !== pattern[j]) {
        break;
      }
    }
    if (j === pattern.length) {
      return i;
    }
  }
  return -1;
}

console.log(naiveSearch('hello world', 'bye'));

A -1

B 0

C 5

D undefined

💡 Hint

If the pattern is not found, what does the function return?

The function returns -1 when the pattern is not found in the text.

🧠 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^2)

C O(m^2)

D O(n + m)

💡 Hint

Consider that for each position in the text, the pattern is checked character by character.

The naive algorithm checks each position in the text and compares up to m characters, leading to O(n * m) time in the worst case.

❓ Predict Output

advanced

Output of Naive Pattern Matching with Multiple Matches

What will be the output of this code that finds all occurrences of a pattern in a text using naive pattern matching?

DSA Javascript

function naiveSearchAll(text, pattern) {
  const result = [];
  for (let i = 0; i <= text.length - pattern.length; i++) {
    let j;
    for (j = 0; j < pattern.length; j++) {
      if (text[i + j] !== pattern[j]) {
        break;
      }
    }
    if (j === pattern.length) {
      result.push(i);
    }
  }
  return result;
}

console.log(naiveSearchAll('ababa', 'aba'));

A [0]

B []

C [1, 3]

D [0, 2]

💡 Hint

Look for all starting indices where 'aba' appears in 'ababa'.

The pattern 'aba' appears starting at indices 0 and 2 in 'ababa'.

🔧 Debug

expert

Identify the Bug in Naive Pattern Matching Implementation

The following code is intended to find the first occurrence of a pattern in a text using naive pattern matching. However, it sometimes returns incorrect results. What is the bug?

DSA Javascript

function naiveSearchBug(text, pattern) {
  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) {
      return i;
    }
  }
  return -1;
}

console.log(naiveSearchBug('abracadabra', 'cada'));

A The inner while loop should reset j to 0 inside the outer loop.

B The loop condition should be i <= text.length - pattern.length to include last possible start index.

C The function should return -1 only if pattern length is zero.

D The comparison text[i + j] === pattern[j] should use != instead of ===.

💡 Hint

Check the loop boundary for the outer loop to ensure all possible positions are checked.

The outer loop stops too early because it uses < instead of <=, missing the last valid start index.

Practice

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

easy

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

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

C. It sorts the text before searching for 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 every position in the text.

2. Step 2: Compare with other methods

   Other methods like hashing or trees are not part of the naive approach.

3. Final Answer:

   It checks 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 advanced algorithms
• Thinking naive sorts the text
• Assuming naive uses data structures like trees

2. Which of the following is the correct syntax to start a loop for naive pattern matching in JavaScript?
for (___; i <= text.length - pattern.length; i++)

easy

A. const i = 0

B. var i = 1

C. let i = 0

D. i = 0

Solution

1. Step 1: Identify loop initialization

   The loop variable must start at 0 to check from the beginning of the text.

2. Step 2: Choose correct declaration

   Using 'let' is correct for block scope and allows incrementing i.

3. Final Answer:

   let i = 0 -> Option C

4. Quick Check:

   Loop start = let i = 0 [OK]

Hint: Use 'let' to declare loop variable starting at zero [OK]

Common Mistakes:

• Using 'const' which cannot be incremented
• Starting loop at 1 instead of 0
• Not declaring variable with let or var

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

function naiveSearch(text, pattern) {
  let count = 0;
  for (let i = 0; i <= text.length - pattern.length; i++) {
    let j;
    for (j = 0; j < pattern.length; j++) {
      if (text[i + j] !== pattern[j]) break;
    }
    if (j === pattern.length) count++;
  }
  return count;
}

console.log(naiveSearch('abababa', 'aba'));

medium

A. 3

B. 2

C. 1

D. 0

Solution

1. Step 1: Check all pattern matches in text

   Positions checked: 0,1,2,3,4. Matches at 0 ('aba'), 2 ('aba'), and 4 ('aba').

2. Step 2: Count total matches

   There are 3 matches of 'aba' in 'abababa'.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Count matches = 3 [OK]

Hint: Count overlapping matches carefully [OK]

Common Mistakes:

• Missing overlapping matches
• Counting only non-overlapping occurrences
• Off-by-one errors in loop limits

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

function search(text, pattern) {
  for (let i = 0; i < text.length; i++) {
    let j = 0;
    while (j < pattern.length && text[i + j] === pattern[j]) {
      j++;
    }
    if (j === pattern.length) return i;
  }
  return -1;
}

medium

A. j should be declared with var instead of let

B. Loop condition should be i <= text.length - pattern.length

C. Return -1 should be inside the for loop

D. While loop condition should use || instead of &&

Solution

1. Step 1: Analyze loop range

   The outer loop runs till i < text.length, which can cause out-of-bound access when i + j exceeds text length.

2. Step 2: Correct loop condition

   It should be i <= text.length - pattern.length to avoid overflow.

3. Final Answer:

   Loop condition should be i <= text.length - pattern.length -> Option B

4. Quick Check:

   Loop limit fix = i <= text.length - pattern.length [OK]

Hint: Limit loop to avoid index overflow [OK]

Common Mistakes:

• Ignoring index overflow causing runtime errors
• Misplacing return statements
• Wrong logical operators in conditions

5. Given a text and a pattern, how can you modify the naive pattern matching algorithm to count only non-overlapping occurrences of the pattern in the text?

hard

A. Use recursion to find matches

B. Use a hash function to skip characters

C. Sort the text before searching

D. After finding a match, increment the outer loop index by pattern length instead of 1

Solution

1. Step 1: Understand overlapping vs non-overlapping

   Naive checks every position, counting overlapping matches. To avoid overlap, skip ahead after a match.

2. Step 2: Modify loop increment

   When a match is found, increase the index by pattern length to jump past the matched substring.

3. Final Answer:

   After finding a match, increment the outer loop index by pattern length instead of 1 -> Option D

4. Quick Check:

   Skip matched length to avoid overlap [OK]

Hint: Jump by pattern length after match to avoid overlaps [OK]

Common Mistakes:

• Trying to sort text which doesn't help
• Using hashing which is unrelated here
• Recursion adds complexity without solving overlap