String Pattern Matching Naive in DSA Go - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to start checking the pattern at the correct index in the text.

DSA Go

for i := 0; i <= len(text) - len(pattern); i++ {
    match := true
    for j := 0; j < len(pattern); j++ {
        if text[i + [1]] != pattern[j] {
            match = false
            break
        }
    }
    if match {
        fmt.Println("Pattern found at index", i)
    }
}

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

Aj

B0

Ci

Dlen(pattern)

Attempts:

3 left

💡 Hint

Common Mistakes

Using i instead of j inside the inner loop index calculation.

Using 0 which always compares the first character of text.

Using len(pattern) which is out of range.

The inner loop compares characters of the pattern with the text starting at index i. We add j to i to check the correct character in the text.

2fill in blank

medium

Complete the code to correctly check if the pattern matches the text at the current position.

DSA Go

for i := 0; i <= len(text) - len(pattern); i++ {
    match := true
    for j := 0; j < len(pattern); j++ {
        if text[i + j] != [1] {
            match = false
            break
        }
    }
    if match {
        fmt.Println("Pattern found at index", i)
    }
}

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

Apattern[i]

Btext[j]

Ctext[i]

Dpattern[j]

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing text characters with each other instead of with pattern.

Using wrong indices for pattern or text.

We compare the character at pattern[j] with the character at text[i + j] to check for a match.

3fill in blank

hard

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

DSA Go

for i := 0; i < [1]; i++ {
    match := true
    for j := 0; j < len(pattern); j++ {
        if text[i + j] != pattern[j] {
            match = false
            break
        }
    }
    if match {
        fmt.Println("Pattern found at index", i)
    }
}

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

Alen(text) - len(pattern) + 1

Blen(text) - len(pattern)

Clen(text)

Dlen(pattern)

Attempts:

3 left

💡 Hint

Common Mistakes

Using len(text) alone causes out-of-range errors.

Using len(text) - len(pattern) excludes the last valid index.

The loop must run until i is at most len(text) - len(pattern) to avoid accessing beyond text length. Using +1 ensures the last valid index is included.

4fill in blank

hard

Fill both blanks to create a map of pattern characters to their last index in the pattern.

DSA Go

lastIndex := make(map[rune]int)
for [1], ch := range pattern {
    lastIndex[ch] = [2]
}

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

Ai

Bch

Cj

Dindex

Attempts:

3 left

💡 Hint

Common Mistakes

Using character variable instead of index for last occurrence.

Using undefined variable names.

We use 'i' as the index variable in the range loop and assign it as the last index for each character.

5fill in blank

hard

Fill all three blanks to print all starting indices where the pattern is found in the text.

DSA Go

matches := []int{}
for i := 0; i <= len(text) - len(pattern); i++ {
    match := true
    for j := 0; j < len(pattern); j++ {
        if text[i + j] != pattern[j] {
            match = false
            break
        }
    }
    if match {
        matches = append(matches, [1])
    }
}
for _, idx := range matches {
    fmt.Println("Pattern found at index", [2])
}
fmt.Println("Total matches:", [3])

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

Ai

Bidx

Clen(matches)

Dj

Attempts:

3 left

💡 Hint

Common Mistakes

Appending wrong variable to matches.

Printing wrong variable in the loop.

Printing a variable not representing total matches.

Append the current index i to matches. Then print each index stored in idx. Finally, print the total number of matches using len(matches).

Practice

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

easy

A. Check every possible position in the text for the pattern

B. Use a hash function to find the pattern quickly

C. Preprocess the pattern to skip some comparisons

D. Sort the text and pattern before matching

Solution

1. Step 1: Understand naive matching approach

   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

   Other methods like hashing or preprocessing are not part of the naive approach.

3. Final Answer:

   Check every possible position in the text for the pattern -> Option A

4. Quick Check:

   Naive = Check all positions [OK]

Hint: Naive means try all positions one by one [OK]

Common Mistakes:

• Thinking naive uses hashing
• Assuming pattern preprocessing is done
• Believing text is sorted first

2. Which of the following Go code snippets correctly starts the outer loop for naive string pattern matching?

easy

A. for i := 0; i <= len(text)-len(pattern); i++ {

B. for i := 0; i < len(text); i++ {

C. for i := 1; i <= len(text); i++ {

D. for i := 0; i < len(pattern); i++ {

Solution

1. Step 1: Determine loop range for matching

   The outer loop must run from 0 to len(text)-len(pattern) to avoid out-of-range errors.

2. Step 2: Check each option

   for i := 0; i <= len(text)-len(pattern); i++ { correctly uses i <= len(text)-len(pattern). Others either go too far or use wrong limits.

3. Final Answer:

   for i := 0; i <= len(text)-len(pattern); i++ { -> Option A

4. Quick Check:

   Loop till text length minus pattern length [OK]

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

Common Mistakes:

• Looping beyond valid start positions
• Starting loop from 1 instead of 0
• Using pattern length as loop limit

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

text := "banana"
pattern := "ana"
count := 0
for i := 0; i <= len(text)-len(pattern); i++ {
  j := 0
  for j < len(pattern) && text[i+j] == pattern[j] {
    j++
  }
  if j == len(pattern) {
    count++
  }
}
fmt.Println(count)

medium

A. 1

B. 3

C. 0

D. 2

Solution

1. Step 1: Identify pattern matches in text

   Check each position in "banana" for "ana": positions 1-3 and 3-5 match.

2. Step 2: Count matches

   Two matches found, so count is 2.

3. Final Answer:

   2 -> Option D

4. Quick Check:

   "ana" appears twice in "banana" [OK]

Hint: Count all exact matches sliding over text [OK]

Common Mistakes:

• Counting overlapping matches incorrectly
• Off-by-one errors in loop limits
• Assuming only first match counts

4. The following Go code tries to count pattern occurrences but has a bug. What is the bug?

text := "abcabcabc"
pattern := "abc"
count := 0
for i := 0; i < len(text)-len(pattern); i++ {
  j := 0
  for j < len(pattern) && text[i+j] == pattern[j] {
    j++
  }
  if j == len(pattern) {
    count++
  }
}
fmt.Println(count)

medium

A. The inner loop condition is wrong

B. The outer loop should use <= instead of <

C. The count variable is not initialized

D. The pattern length is not checked

Solution

1. Step 1: Analyze outer loop range

   The loop runs from 0 to len(text)-len(pattern)-1, missing last valid start index.

2. Step 2: Correct loop condition

   Changing < to <= includes last position, fixing missed matches.

3. Final Answer:

   The outer loop should use <= instead of < -> Option B

4. Quick Check:

   Loop must cover last valid start index [OK]

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

Common Mistakes:

• Using < instead of <= in outer loop
• Ignoring last possible match position
• Misunderstanding loop boundaries

5. Given the text "abracadabra" and pattern "abra", how many times will the naive algorithm find the pattern if overlapping matches are counted? Use the naive approach code below:

text := "abracadabra"
pattern := "abra"
count := 0
for i := 0; i <= len(text)-len(pattern); i++ {
  j := 0
  for j < len(pattern) && text[i+j] == pattern[j] {
    j++
  }
  if j == len(pattern) {
    count++
  }
}
fmt.Println(count)

hard

A. 3

B. 1

C. 2

D. 4

Solution

1. Step 1: Identify all pattern matches including overlaps

   "abra" appears at positions 0-3 and 7-10 in "abracadabra".

2. Step 2: Count total matches

   Two matches found, so count is 2.

3. Final Answer:

   2 -> Option C

4. Quick Check:

   "abra" occurs twice overlapping allowed [OK]

Hint: Check all positions including overlaps [OK]

Common Mistakes:

• Counting only first match
• Missing second overlapping match
• Confusing substring positions