Substring Search Patterns in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Naive Substring Search

What is the output of the following JavaScript code that searches for a pattern in a text using a naive approach?

DSA Javascript

function naiveSearch(text, pattern) {
  const result = [];
  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) {
      result.push(i);
    }
  }
  return result;
}

console.log(naiveSearch('abracadabra', 'abra'));

A [0, 7]

B [0, 3, 7]

C [3, 7]

D [7]

💡 Hint

Check where the substring 'abra' appears in 'abracadabra'.

The pattern 'abra' appears at index 0 and again at index 7 in the text 'abracadabra'. The naive search finds both occurrences and returns their starting indices.

❓ Predict Output

intermediate

Output of KMP Prefix Table Construction

What is the output of the prefix table (also called lps array) constructed by the KMP algorithm for the pattern 'ababc'?

DSA Javascript

function computeLPS(pattern) {
  const lps = Array(pattern.length).fill(0);
  let length = 0;
  let i = 1;
  while (i < pattern.length) {
    if (pattern[i] === pattern[length]) {
      length++;
      lps[i] = length;
      i++;
    } else {
      if (length !== 0) {
        length = lps[length - 1];
      } else {
        lps[i] = 0;
        i++;
      }
    }
  }
  return lps;
}

console.log(computeLPS('ababc'));

A [0, 1, 0, 1, 0]

B [0, 1, 2, 0, 1]

C [0, 0, 1, 2, 0]

D [0, 0, 0, 1, 2]

💡 Hint

The lps array stores the length of the longest prefix which is also suffix for each prefix of the pattern.

The lps array for 'ababc' is [0, 0, 1, 2, 0]. This means at index 2, the longest prefix-suffix length is 1 ('a'), at index 3 it is 2 ('ab'), and at index 4 it resets to 0.

❓ Predict Output

advanced

Output of Rabin-Karp Hash Matches

What is the output of the Rabin-Karp substring search function below when searching for 'test' in 'this is a test text for test'?

DSA Javascript

function rabinKarp(text, pattern) {
  const result = [];
  const prime = 101;
  const m = pattern.length;
  const n = text.length;
  let patternHash = 0;
  let textHash = 0;
  let h = 1;

  for (let i = 0; i < m - 1; i++) {
    h = (h * 256) % prime;
  }

  for (let i = 0; i < m; i++) {
    patternHash = (256 * patternHash + pattern.charCodeAt(i)) % prime;
    textHash = (256 * textHash + text.charCodeAt(i)) % prime;
  }

  for (let i = 0; i <= n - m; i++) {
    if (patternHash === textHash) {
      let match = true;
      for (let j = 0; j < m; j++) {
        if (text[i + j] !== pattern[j]) {
          match = false;
          break;
        }
      }
      if (match) result.push(i);
    }
    if (i < n - m) {
      textHash = (256 * (textHash - text.charCodeAt(i) * h) + text.charCodeAt(i + m)) % prime;
      if (textHash < 0) textHash += prime;
    }
  }
  return result;
}

console.log(rabinKarp('this is a test text for test', 'test'));

A [10, 24]

B [10]

C [15, 24]

D [5, 10, 24]

💡 Hint

Find all starting indices where 'test' appears exactly in the text.

The substring 'test' appears at index 10 and index 24 in the given text. The Rabin-Karp algorithm finds both positions and returns them.

❓ Predict Output

advanced

Output of Boyer-Moore Bad Character Table

What is the bad character shift table generated by the Boyer-Moore algorithm for the pattern 'example'?

DSA Javascript

function badCharTable(pattern) {
  const table = {};
  for (let i = 0; i < pattern.length - 1; i++) {
    table[pattern[i]] = pattern.length - 1 - i;
  }
  return table;
}

console.log(badCharTable('example'));

A {"e":6,"x":1,"a":2,"m":3,"p":4,"l":5}

B {"e":0,"x":1,"a":2,"m":3,"p":4,"l":5}

C {"e":0,"x":5,"a":4,"m":3,"p":2,"l":1}

D {"e":6,"x":5,"a":4,"m":3,"p":2,"l":1}

💡 Hint

The bad character table stores how far to shift when a mismatch occurs on a character.

The bad character table for 'example' assigns shifts based on the last occurrence of each character except the last one. For example, 'e' at index 0 gets shift 6 (7 - 1 - 0).

🧠 Conceptual

expert

Time Complexity Comparison of Substring Search Algorithms

Which statement correctly compares the average and worst-case time complexities of the naive, KMP, and Rabin-Karp substring search algorithms for a text of length n and pattern of length m?

A Naive: O(n) worst, O(n) average; KMP: O(n*m) worst and average; Rabin-Karp: O(n*m) worst, O(n*m) average

B Naive: O(n*m) worst, O(n*m) average; KMP: O(n) worst and average; Rabin-Karp: O(n*m) worst, O(n+m) average

C Naive: O(n*m) worst, O(n) average; KMP: O(n*m) worst, O(n*m) average; Rabin-Karp: O(n) worst, O(n) average

D Naive: O(n*m) worst, O(n*m) average; KMP: O(n*m) worst, O(n) average; Rabin-Karp: O(n) worst, O(n+m) average

💡 Hint

Consider how each algorithm behaves in worst and average cases.

The naive algorithm can take O(n*m) time in both worst and average cases. KMP runs in O(n) time always due to its prefix table. Rabin-Karp has average O(n+m) due to hashing but worst O(n*m) if many hash collisions occur.

Practice

1. What does the indexOf method do when used on a string in JavaScript?

easy

A. Converts the string to uppercase

B. Replaces a substring with another string

C. Splits the string into an array of substrings

D. Finds the position of the first occurrence of a substring

Solution

1. Step 1: Understand the purpose of indexOf

   The indexOf method searches a string for a specified substring and returns the position of its first occurrence.

2. Step 2: Confirm behavior on strings

   If the substring is found, it returns the zero-based index; if not found, it returns -1.

3. Final Answer:

   Finds the position of the first occurrence of a substring -> Option D

4. Quick Check:

   indexOf = position of substring [OK]

Hint: Remember: indexOf returns position or -1 if not found [OK]

Common Mistakes:

• Confusing indexOf with replace method
• Thinking indexOf splits the string
• Assuming indexOf changes the string case

2. Which of the following is the correct syntax to check if the substring 'cat' exists in the string text using includes method?

easy

A. text.include('cat')

B. includes(text, 'cat')

C. text.includes('cat')

D. text.contains('cat')

Solution

1. Step 1: Recall the correct method name

   The correct method to check substring presence is includes, called on the string object.

2. Step 2: Verify syntax

   The syntax is string.includes(substring), so text.includes('cat') is correct.

3. Final Answer:

   text.includes('cat') -> Option C

4. Quick Check:

   Correct method call syntax = text.includes('cat') [OK]

Hint: Use string.includes(substring) to check presence [OK]

Common Mistakes:

• Using wrong method name like include or contains
• Calling includes as a standalone function
• Passing arguments in wrong order

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

const text = 'hello world';
const pos = text.indexOf('o');
console.log(pos);

medium

A. 4

B. 5

C. -1

D. 6

Solution

1. Step 1: Identify the string and substring

   The string is 'hello world' and the substring searched is 'o'.

2. Step 2: Find the first occurrence of 'o'

   Counting from zero: h(0) e(1) l(2) l(3) o(4) (space 5) w(6) o(7). The first 'o' is at index 4.

3. Step 3: Verify the output

   The code uses indexOf('o') which returns the first occurrence index, which is 4.

4. Final Answer:

   4 -> Option A

5. Quick Check:

   First 'o' index = 4 [OK]

Hint: Count string index from zero to find first substring position [OK]

Common Mistakes:

• Counting index starting from 1 instead of 0
• Confusing second 'o' position with first
• Assuming indexOf returns -1 if substring exists

4. The following code is intended to check if the substring 'test' exists in str. What is the error?

const str = 'this is a test';
if (str.indexOf == 'test') {
  console.log('Found');
} else {
  console.log('Not Found');
}

medium

A. The variable str is not declared properly

B. indexOf is used without parentheses, so it compares function to string

C. The if condition should use === instead of ==

D. The substring 'test' is misspelled

Solution

1. Step 1: Analyze the use of indexOf

   The code uses str.indexOf without parentheses, so it refers to the function itself, not the result of calling it.

2. Step 2: Understand the comparison

   Comparing a function to a string ('test') is always false, so the condition is incorrect.

3. Final Answer:

   indexOf is used without parentheses, so it compares function to string -> Option B

4. Quick Check:

   Missing parentheses on indexOf causes error [OK]

Hint: Always call indexOf with parentheses and substring argument [OK]

Common Mistakes:

• Forgetting parentheses on indexOf
• Using wrong comparison operator
• Assuming indexOf returns boolean directly

5. You want to find all starting positions of the substring 'ana' in the string 'banana'. Which approach correctly finds all positions?

hard

A. Use a loop with indexOf and update the start position after each find

B. Use includes repeatedly until it returns false

C. Use lastIndexOf to find all positions from the end

D. Use replace to remove substring and count occurrences

Solution

1. Step 1: Understand the problem of multiple occurrences

   To find all positions, you must repeatedly search starting after the last found position.

2. Step 2: Use a loop with indexOf and update start

   Use indexOf('ana', start) in a loop, updating start to position + 1 each time until no more found.

3. Final Answer:

   Use a loop with indexOf and update the start position after each find -> Option A

4. Quick Check:

   Loop + indexOf with updated start = all positions [OK]

Hint: Loop with indexOf(start) to find all substring positions [OK]

Common Mistakes:

• Using includes which returns only true/false
• Using lastIndexOf which finds only last occurrence
• Using replace which changes string and loses positions