String Pattern Matching Naive in DSA Javascript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind the Naive String Pattern Matching algorithm?

It checks for the pattern by sliding it over the text one by one and compares characters one by one until a match is found or the text ends.

intermediate

What is the worst-case time complexity of the Naive String Pattern Matching algorithm?

O(m * n), where m is the length of the pattern and n is the length of the text, because it may check every character of the text for every character of the pattern.

beginner

In Naive String Pattern Matching, what happens when a mismatch occurs during comparison?

The algorithm shifts the pattern by one position to the right and starts comparing again from the first character of the pattern.

intermediate

Why is the Naive String Pattern Matching algorithm not efficient for large texts and patterns?

Because it may repeatedly compare the same characters many times, leading to a high number of comparisons especially when the pattern and text have many repeated characters.

beginner

Show a simple JavaScript code snippet for Naive String Pattern Matching.

function naiveSearch(text, pattern) {
  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) return i; // pattern found at index i
  }
  return -1; // pattern not found
}

What does the Naive String Pattern Matching algorithm do when it finds a mismatch?

A Shifts the pattern by the length of the pattern

B Stops the search immediately

C Skips to the next character in the text without shifting

D Shifts the pattern by one position and restarts comparison

When a mismatch occurs, the algorithm shifts the pattern by one position to the right and starts comparing again from the first character.

What is the best case time complexity of the Naive String Pattern Matching algorithm?

A O(m * n)

B O(n)

C O(m + n)

D O(1)

In the best case, the pattern matches immediately or mismatches early, so the algorithm runs in O(n) time.

Which of the following is true about the Naive String Pattern Matching algorithm?

A It uses preprocessing to skip characters

B It uses a hash function to find matches

C It compares characters one by one without preprocessing

D It only works for numeric strings

The naive algorithm compares characters one by one without any preprocessing or hashing.

If the text length is 100 and the pattern length is 5, what is the maximum number of comparisons in the worst case?

A 500

B 95

C 105

D 100

Worst case comparisons are m * n = 5 * 100 = 500.

Which scenario causes the Naive String Pattern Matching algorithm to perform poorly?

A Pattern and text have many repeated characters

B Pattern is longer than text

C Pattern is empty

D Text contains only unique characters

Repeated characters cause many repeated comparisons, leading to poor performance.

Explain how the Naive String Pattern Matching algorithm works step-by-step.

Think about how you would find a word in a book by checking each letter.

Describe the time complexity of the Naive String Pattern Matching algorithm and why it can be inefficient.

Consider how many times characters might be compared in the worst case.

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