String Pattern Matching Naive in DSA Javascript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to start the outer loop from the first character of the text.

DSA Javascript

for (let i = [1]; i <= text.length - pattern.length; i++) {
  // matching logic
}

Drag options to blanks, or click blank then click option'

A0

Bpattern.length

Ctext.length

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Starting loop from 1 misses checking the pattern at the very beginning of the text.

Starting loop from pattern.length skips initial positions.

The outer loop should start from index 0 to check all possible starting positions in the text.

2fill in blank

medium

Complete the code to start the inner loop from the first character of the pattern.

DSA Javascript

for (let j = [1]; j < pattern.length; j++) {
  if (text[i + j] !== pattern[j]) {
    break;
  }
}

Drag options to blanks, or click blank then click option'

A0

Bpattern.length

C1

Dtext.length

Attempts:

3 left

💡 Hint

Common Mistakes

Starting inner loop from 1 skips the first character of the pattern.

Using text.length as start index causes out-of-range errors.

The inner loop should start from 0 to compare each character of the pattern from the beginning.

3fill in blank

hard

Fix the error in the condition to check if the pattern matches completely.

DSA Javascript

if (j === [1]) {
  result.push(i);
}

Drag options to blanks, or click blank then click option'

Apattern.length - 1

Bi + j

Ctext.length

Dpattern.length

Attempts:

3 left

💡 Hint

Common Mistakes

Using pattern.length - 1 causes off-by-one error.

Comparing j to text.length is incorrect.

When j equals pattern.length, it means all characters matched successfully.

4fill in blank

hard

Fill both blanks to complete the naive string matching function.

DSA Javascript

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

Drag options to blanks, or click blank then click option'

A0

Bpattern.length

Ctext.length

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Starting outer loop at 1 misses first position.

Using text.length in inner loop causes errors.

The outer loop starts at 0, and the inner loop runs up to pattern.length to check all characters.

5fill in blank

hard

Fill all three blanks to return all starting indices where the pattern is found in the text.

DSA Javascript

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

Drag options to blanks, or click blank then click option'

A0

Bpattern.length

Dtext.length

Attempts:

3 left

💡 Hint

Common Mistakes

Using text.length instead of pattern.length in inner loop or match check.

Starting outer loop at 1 misses first position.

Start outer loop at 0, inner loop runs to pattern.length, and full match is when j equals pattern.length.

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