String Pattern Matching Naive in DSA Typescript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to check if the pattern matches the substring starting at index i.

DSA Typescript

if (text[i + j] !== pattern[j]) {
  return [1];
}

Drag options to blanks, or click blank then click option'

Afalse

Btrue

Cnull

Dundefined

Attempts:

3 left

💡 Hint

Common Mistakes

Returning true instead of false on mismatch.

Returning null or undefined which are not boolean.

If any character does not match, the function should return false indicating no match at this position.

2fill in blank

medium

Complete the code to return the starting index when the pattern is found.

DSA Typescript

if (j === pattern.length) {
  return [1];
}

Drag options to blanks, or click blank then click option'

A-1

Bj

Cpattern.length

Di

Attempts:

3 left

💡 Hint

Common Mistakes

Returning j which is the pattern length index.

Returning -1 which means not found.

When all characters match, return the starting index i where the pattern begins.

3fill in blank

hard

Fix the error in the loop condition to avoid out-of-bound errors.

DSA Typescript

for (let i = 0; i <= text.length [1] pattern.length; i++) {
  // matching logic
}

Drag options to blanks, or click blank then click option'

A*

B+

C-

D/

Attempts:

3 left

💡 Hint

Common Mistakes

Using + which causes index overflow.

Using * or / which are invalid here.

We subtract pattern.length to ensure the pattern fits inside the text without overflow.

4fill in blank

hard

Fill both blanks to complete the nested loop for naive pattern matching.

DSA Typescript

for (let i = 0; i <= text.length [1] pattern.length; i++) {
  let j = 0;
  for (; j < pattern.length; j++) {
    if (text[i + j] !== pattern[j]) {
      break;
    }
  }
  if (j === [2]) {
    return i;
  }
}

Drag options to blanks, or click blank then click option'

A-

Bpattern.length

Ctext.length

D+

Attempts:

3 left

💡 Hint

Common Mistakes

Using + in outer loop limit causing overflow.

Comparing j to text.length instead of pattern.length.

The outer loop stops at text.length - pattern.length. The inner loop compares up to pattern.length characters.

5fill in blank

hard

Fill all three blanks to complete the naive pattern matching function that returns -1 if not found.

DSA Typescript

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

Drag options to blanks, or click blank then click option'

A-

Bpattern.length

Dtext.length

Attempts:

3 left

💡 Hint

Common Mistakes

Using text.length in inner loop or match check.

Using addition in outer loop limit.

The outer loop limit subtracts pattern length. Both inner loop conditions and match check use pattern.length.

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