String Pattern Matching Naive in DSA Javascript - Build from Scratch

String Pattern Matching Naive

📖 Scenario: You are building a simple search tool that looks for a small word inside a bigger text. This is like finding a word in a book by checking each letter one by one.

🎯 Goal: Build a program that finds all starting positions where a given pattern appears in a text using the naive string 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'.

Use a for loop with variable i to check each possible starting position in text.

Use a nested for loop with variable j to compare characters of pattern with text.

Create an array called positions to store all starting indexes where pattern matches text.

Print the positions array at the end.

💡 Why This Matters

🌍 Real World

Searching for words or phrases inside documents, like finding keywords in a book or searching text in a chat app.

💼 Career

Understanding basic string searching helps in text processing, search engines, and software that needs to find patterns in data.

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 Javascript

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

Hint

Use const to create variables for text and pattern.

2

Create an array to store matching positions

Create an empty array called positions to store the starting indexes where pattern matches text.

DSA Javascript

const text = 'abracadabra';
const pattern = 'abra';
// Create an empty array called positions
// Your code here

Hint

Use [] to create an empty array named positions.

3

Implement the naive pattern matching loops

Use a for loop with variable i from 0 to text.length - pattern.length. Inside it, use a nested for loop with variable j from 0 to pattern.length to compare characters of pattern with text. If all characters match, add i to positions.

DSA Javascript

const text = 'abracadabra';
const pattern = 'abra';
const positions = [];
// Use for loops to find all positions where pattern matches text
// Your code here

Hint

Use two loops: outer loop for each possible start index i, inner loop to check each character j. Use a boolean match to track if all characters match.

4

Print the matching positions

Print the positions array using console.log(positions).

DSA Javascript

const text = 'abracadabra';
const pattern = 'abra';
const positions = [];

for (let i = 0; i <= text.length - pattern.length; i++) {
    let match = true;
    for (let j = 0; j < pattern.length; j++) {
        if (text[i + j] !== pattern[j]) {
            match = false;
            break;
        }
    }
    if (match) {
        positions.push(i);
    }
}
// Print the positions array
// Your code here

Hint

Use console.log(positions) to show the result.

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