String Pattern Matching Naive in DSA Javascript

Mental Model

Check every possible place in the text to see if the pattern matches exactly.

Analogy: Like looking for a small picture in a big photo by sliding it over every spot and checking if it fits perfectly.

Text:  T -> h -> i -> s ->   -> i -> s ->   -> a ->   -> t -> e -> x -> t -> null
Pattern: P -> a -> t -> t -> e -> r -> n -> null

Dry Run Walkthrough

Input: text: 'abcabcabc', pattern: 'abc'

Goal: Find all starting positions in the text where the pattern 'abc' appears exactly.

Step 1: Check text starting at index 0 for pattern match

text: [abc]abcabc
pattern: abc

Why: We start checking from the beginning of the text

Step 2: Compare characters at text[0..2] with pattern[0..2]

text: [abc]abcabc
pattern: abc

Why: Check if substring matches pattern exactly

Step 3: Match found at index 0, record position 0

matches: [0]

Why: All characters matched, so pattern found here

Step 4: Move to index 1 and check for pattern

text: a[bca]bcabc
pattern: abc

Why: Try next position in text

Step 5: Mismatch at text[1] and pattern[0], move to next index

no match at index 1

Why: First characters don't match, no need to check further

Step 6: Check text starting at index 3 for pattern match

text: abc[abc]abc
pattern: abc

Why: Continue sliding pattern over text

Step 7: Match found at index 3, record position 3

matches: [0, 3]

Why: Pattern matches again here

Step 8: Check text starting at index 6 for pattern match

text: abcabc[abc]
pattern: abc

Why: Check last possible position

Step 9: Match found at index 6, record position 6

matches: [0, 3, 6]

Why: Pattern matches at the end

Result:

matches at indices: 0, 3, 6

Annotated Code

DSA Javascript

class StringMatcher {
  constructor(text, pattern) {
    this.text = text;
    this.pattern = pattern;
  }

  naiveSearch() {
    const matches = [];
    const n = this.text.length;
    const m = this.pattern.length;

    for (let i = 0; i <= n - m; i++) {
      let j = 0;
      while (j < m && this.text[i + j] === this.pattern[j]) {
        j++;
      }
      if (j === m) {
        matches.push(i);
      }
    }
    return matches;
  }
}

// Driver code
const text = 'abcabcabc';
const pattern = 'abc';
const matcher = new StringMatcher(text, pattern);
const result = matcher.naiveSearch();
console.log('matches at indices: ' + result.join(', '));

for (let i = 0; i <= n - m; i++) {

slide pattern start index over text from 0 to last possible start

while (j < m && this.text[i + j] === this.pattern[j]) {

compare characters one by one until mismatch or full pattern matched

if (j === m) {

if full pattern matched, record the start index

Output

matches at indices: 0, 3, 6

Complexity Analysis

Time: O(n*m) because for each of the n-m+1 positions in text, we may compare up to m characters

Space: O(k) where k is number of matches found, for storing match indices

vs Alternative: Naive is simpler but slower than advanced algorithms like KMP which run in O(n+m) time

Edge Cases

empty pattern

matches at every index including end (0 to text length)

DSA Javascript

for (let i = 0; i <= n - m; i++) {

pattern longer than text

no matches found because loop does not run

DSA Javascript

for (let i = 0; i <= n - m; i++) {

pattern not in text

empty matches array returned

DSA Javascript

if (j === m) {

When to Use This Pattern

When asked to find all occurrences of a small pattern in a text and no advanced algorithm is required, use naive pattern matching by checking every possible position.

Common Mistakes

Mistake: Not stopping character comparison on first mismatch and continuing unnecessarily
Fix: Use a while loop that breaks immediately when characters differ

Mistake: Looping beyond the last valid start index causing out-of-bound errors
Fix: Limit outer loop to i <= n - m to avoid overflow

Summary

It finds all places where a pattern appears in a text by checking each position one by one.

Use it when you want a simple solution and the text or pattern is small.

The key is to slide the pattern over the text and compare characters until a mismatch or full match.

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