String Pattern Matching Naive in DSA Typescript

Mental Model

Check every possible place in the text where the pattern might start and compare characters one by one.

Analogy: Like looking for a small word in a big book by reading each page from start to end and checking every word until you find a match.

Text:  a b c d a b c d e f
Pattern:    a b c d
Positions to check: [0] [1] [2] [3] [4] [5] [6]

Dry Run Walkthrough

Input: text: 'abcabcd', pattern: 'abcd'

Goal: Find the starting index where 'abcd' appears in 'abcabcd'

Step 1: Check pattern starting at text index 0

text: [a b c a b c d]
pattern: [a b c d]
compare text[0..3] with pattern[0..3]

Why: We start checking from the first character of the text

Step 2: Mismatch found at text index 3 ('a' vs 'd')

text: [a b c a b c d]
pattern: [a b c d]
stop comparing here

Why: Characters do not match, so pattern does not start here

Step 3: Check pattern starting at text index 1

text: a [b c a b c d]
pattern: [a b c d]
compare text[1..4] with pattern[0..3]

Why: Try next position in text

Step 4: Mismatch found at text index 4 ('b' vs 'd')

text: a [b c a b c d]
pattern: [a b c d]
stop comparing here

Why: Characters do not match, so pattern does not start here

Step 5: Check pattern starting at text index 2

text: a b [c a b c d]
pattern: [a b c d]
compare text[2..5] with pattern[0..3]

Why: Try next position in text

Step 6: Mismatch found at text index 5 ('a' vs 'd')

text: a b [c a b c d]
pattern: [a b c d]
stop comparing here

Why: Characters do not match, so pattern does not start here

Step 7: Check pattern starting at text index 3

text: a b c [a b c d]
pattern: [a b c d]
compare text[3..6] with pattern[0..3]

Why: Try next position in text

Step 8: All characters match at text indices 3 to 6

text: a b c [a b c d]
pattern: [a b c d]
pattern found starting at index 3

Why: Pattern matches fully here, so we found the answer

Result:

text: a b c [a b c d]
pattern found starting at index 3

Annotated Code

DSA Typescript

class NaivePatternMatcher {
  static search(text: string, pattern: string): number {
    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
  }
}

// Driver code
const text = 'abcabcd';
const pattern = 'abcd';
const index = NaivePatternMatcher.search(text, pattern);
if (index !== -1) {
  console.log(`Pattern found at index ${index}`);
} else {
  console.log('Pattern not found');
}

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

Try each possible start position in text where pattern can fit

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

Compare characters one by one until mismatch or full match

if (j === m) {

If full pattern matched, return current start index

Output

Pattern found at index 3

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(1) because no extra space is used except variables

vs Alternative: Compared to advanced algorithms like KMP which run in O(n), naive is slower but simpler to implement

Edge Cases

Empty pattern

Returns 0 immediately since empty pattern matches at start

DSA Typescript

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

Pattern longer than text

Loop does not run, returns -1 meaning no match

DSA Typescript

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

Pattern not found in text

Returns -1 after checking all positions

DSA Typescript

return -1; // pattern not found

When to Use This Pattern

When you need to find if a small string appears inside a bigger string and no advanced preprocessing is required, the naive pattern matching is the first simple approach to try.

Common Mistakes

Mistake: Not stopping the inner comparison loop on mismatch and continuing to compare unnecessary characters
Fix: Use a while loop that breaks immediately when characters differ

Mistake: Checking positions in text beyond where pattern can fit
Fix: Limit outer loop to n - m to avoid out-of-bound errors

Summary

Checks every possible position in the text to find the pattern by comparing characters one by one.

Use when you want a simple, easy-to-understand method for pattern searching without preprocessing.

The key insight is to try matching the pattern starting at each text index until a full match is found or all positions are checked.

Practice

1. What does the naive string pattern matching algorithm do?

easy

A. It sorts the text before searching for the pattern.

B. It uses a hash function to find the pattern quickly.

C. It checks every possible position in the text to find 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 each position in the text one by one.

2. Step 2: Compare with other methods

   Unlike hashing or trees, naive does not use extra data structures or preprocessing.

3. Final Answer:

   It checks every possible position in the text to find the pattern. -> Option C

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 it sorts text before matching
• Assuming it uses trees or graphs

2. Which of the following is the correct syntax to start a loop from 0 to text.length - pattern.length in TypeScript for naive pattern matching?

easy

A. for (let i = 0; i < pattern.length; i++)

B. for (let i = 1; i < text.length - pattern.length; i++)

C. for (let i = 0; i < text.length; i++)

D. for (let i = 0; i <= text.length - pattern.length; i++)

Solution

1. Step 1: Determine loop range for matching

   The loop must start at 0 and go up to text.length - pattern.length inclusive to check all valid positions.

2. Step 2: Check syntax correctness

   for (let i = 0; i <= text.length - pattern.length; i++) uses <= and correct boundaries, others either start at 1 or wrong limits.

3. Final Answer:

   for (let i = 0; i <= text.length - pattern.length; i++) -> Option D

4. Quick Check:

   Loop from 0 to text.length - pattern.length inclusive [OK]

Hint: Loop till text length minus pattern length inclusive [OK]

Common Mistakes:

• Starting loop at 1 instead of 0
• Looping beyond valid range causing errors
• Using pattern length as loop limit

3. What will be the output of the following TypeScript code?

const text = "abcabcabc";
const pattern = "abc";
let count = 0;
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) {
    count++;
  }
}
console.log(count);

medium

A. 3

B. 2

C. 1

D. 0

Solution

1. Step 1: Identify pattern occurrences in text

   The pattern "abc" appears at positions 0, 3, and 6 in the text "abcabcabc".

2. Step 2: Count matches using the loop

   The code increments count each time the pattern matches fully, so count becomes 3.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Pattern "abc" occurs 3 times [OK]

Hint: Count matches by checking each position fully [OK]

Common Mistakes:

• Counting overlapping matches incorrectly
• Stopping after first match
• Off-by-one errors in loop

4. Find the error in this naive pattern matching code snippet:

const text = "hellohello";
const pattern = "lo";
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) {
    console.log(i);
  }
}

medium

A. The while condition should use || instead of &&.

B. The loop should use <= instead of < to include last position.

C. The pattern length is incorrect.

D. The console.log should be outside the loop.

Solution

1. Step 1: Check loop boundary for matching

   The loop ends at text.length - pattern.length - 1 due to < operator, missing last valid position.

2. Step 2: Correct loop condition

   Changing < to <= includes the last position where pattern can match.

3. Final Answer:

   The loop should use <= instead of < to include last position. -> Option B

4. Quick Check:

   Loop boundary must cover all valid start indices [OK]

Hint: Use <= to cover last possible start index [OK]

Common Mistakes:

• Using < instead of <= in loop
• Changing && to || in while condition
• Misplacing console.log outside loop

5. Given a text and a pattern, how can you modify the naive string pattern matching algorithm to count overlapping occurrences of the pattern in the text? For example, text = "aaaaa" and pattern = "aaa" should return 3.

hard

A. After finding a match, move the start index by 1 instead of pattern length.

B. After finding a match, move the start index by pattern length.

C. Use a hash function to detect overlaps.

D. Skip checking overlapping positions to improve speed.

Solution

1. Step 1: Understand overlapping matches

   Overlapping means matches can start inside a previous match, so we must check every position.

2. Step 2: Adjust index increment after match

   Instead of jumping by pattern length, increment start index by 1 to check next position for overlaps.

3. Final Answer:

   After finding a match, move the start index by 1 instead of pattern length. -> Option A

4. Quick Check:

   Increment by 1 to count overlaps [OK]

Hint: Move start by 1 after match to count overlaps [OK]

Common Mistakes:

• Skipping positions after match causing missed overlaps
• Using hash functions unnecessarily
• Trying to skip overlaps to speed up