Why String Pattern Matching Naive in DSA Javascript?

The Big Idea

What if you could find any word in a huge text without reading every letter yourself?

The Scenario

Imagine you have a huge book and you want to find every place where a certain word appears. You try to do it by reading every page and checking every word one by one manually.

The Problem

This manual way is very slow and tiring. You can easily miss some places or make mistakes because you have to remember where you looked and what you checked. It takes a lot of time and effort.

The Solution

The naive string pattern matching method helps by automating this search. It checks every possible place in the text where the pattern could start and compares characters one by one. This way, you don't have to do it manually, and it guarantees finding all matches.

Before vs After

✗ Before

const text = 'hello world';
// Manually check each position for 'world'
if (text.substring(6, 11) === 'world') {
  console.log('Found at 6');
}

✓ After

function naiveSearch(text, pattern) {
  let matches = [];
  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) {
      matches.push(i);
    }
  }
  return matches;
}

What It Enables

This method enables automatic and complete searching of patterns inside texts, saving time and avoiding human errors.

Real Life Example

Finding a specific word or phrase in a large document or searching for a DNA sequence inside a long genetic code.

Key Takeaways

Manual searching is slow and error-prone.

Naive pattern matching automates checking every possible position.

It guarantees finding all occurrences of the pattern.

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