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

Recall & Review

beginner

What is the main idea behind the naive string pattern matching algorithm?

The naive algorithm checks for the pattern at every possible position in the text by comparing characters one by one until a match is found or all positions are checked.

beginner

What is the worst-case time complexity of the naive string pattern matching algorithm?

The worst-case time complexity is 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 pattern at every position in the text.

beginner

In the naive string pattern matching, what happens when a mismatch occurs during comparison?

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

beginner

Show the TypeScript function signature for a naive string pattern matching function.

function naivePatternMatch(text: string, pattern: string): number[]

beginner

Why is the naive string pattern matching algorithm not efficient for large texts and patterns?

Because it checks every position in the text and compares all characters of the pattern, leading to many repeated comparisons and a high time cost in the worst case.

What does the naive string pattern matching algorithm do when it finds a mismatch?

A Uses a preprocessed table to jump ahead

B Stops immediately and returns no match

C Skips multiple characters in the text

D Shifts the pattern by one position and restarts comparison

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

What is the time complexity of the naive string pattern matching algorithm in the worst case?

A O(m * n)

B O(m + n)

C O(n log m)

D O(m^2)

The naive algorithm can check every character of the pattern at every position in the text, leading to O(m * n) complexity.

Which of the following best describes the naive string pattern matching approach?

A Preprocesses the pattern to skip characters

B Checks all possible positions in the text one by one

C Uses hashing to find matches quickly

D Builds a finite automaton for the pattern

The naive approach tries matching the pattern at every position in the text without preprocessing.

If the text is 'aaaaa' and the pattern is 'aaa', how many matches will the naive algorithm find?

A 1

B 2

C 3

D 4

The pattern 'aaa' appears starting at positions 0, 1, and 2 in the text.

Which data structure is primarily used in the naive string pattern matching algorithm?

A Array or string indexing

B Stack

C Hash table

D Trie

The naive algorithm uses simple array or string indexing to compare characters.

Explain how the naive string pattern matching algorithm works step-by-step.

Think about sliding the pattern over the text and checking each position.

Describe the main disadvantage of the naive string pattern matching algorithm and why it happens.

Consider how many times characters are compared in worst case.

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