String Pattern Matching Naive in DSA Typescript - Build from Scratch

String Pattern Matching Naive

📖 Scenario: Imagine you have a long text message and you want to find if a smaller word or pattern appears inside it. This is like looking for a friend's name in a long letter.

🎯 Goal: You will build a simple program that checks if a small pattern exists inside a bigger text using a straightforward method called naive pattern matching.

📋 What You'll Learn

Create a string variable called text with the exact value 'hello world'

Create a string variable called pattern with the exact value 'world'

Write a function called naivePatternMatch that takes text and pattern as inputs and returns the starting index of the pattern in the text or -1 if not found

Use a simple loop to check each possible position in text where pattern could start

Print the result of calling naivePatternMatch(text, pattern)

💡 Why This Matters

🌍 Real World

Searching for words or phrases inside documents, messages, or data streams is common in text editors, search engines, and chat apps.

💼 Career

Understanding basic pattern matching helps in roles like software development, data analysis, and quality assurance where text processing is needed.

1

Create the text string

Create a string variable called text and set it to 'hello world'

DSA Typescript

# Your code here

Hint

Use const text = 'hello world'; to create the text string.

2

Create the pattern string

Create a string variable called pattern and set it to 'world'

DSA Typescript

const text = 'hello world';
# Your code here

Hint

Use const pattern = 'world'; to create the pattern string.

3

Write the naive pattern matching function

Write a function called naivePatternMatch that takes text and pattern as parameters and uses a for loop with variable i to check each possible starting position. Inside it, use another for loop with variable j to compare characters. Return the index i if the pattern matches, otherwise return -1 after the loops.

DSA Typescript

const text = 'hello world';
const pattern = 'world';

# Your code here

Hint

Use two loops: outer loop with i for positions, inner loop with j for characters. Return i if all characters match, else return -1.

4

Print the pattern match result

Print the result of calling naivePatternMatch(text, pattern) using console.log

DSA Typescript

const text = 'hello world';
const pattern = 'world';

function naivePatternMatch(text: string, pattern: string): number {
    for (let i = 0; i <= text.length - pattern.length; i++) {
        let j = 0;
        for (; j < pattern.length; j++) {
            if (text[i + j] !== pattern[j]) {
                break;
            }
        }
        if (j === pattern.length) {
            return i;
        }
    }
    return -1;
}

# Your code here

Hint

Use console.log(naivePatternMatch(text, pattern)); to show the result.

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