---

CS323 - Homework on String matching and indexing

---

• KMP Algorithm (20 pts)
  • Compute the failure function for the pattern abababab (5 pts)
    • f(0) =
    • f(1) =
    • f(2) =
    • f(3) =
    • f(4) =
    • f(5) =
    • f(6) =
    • f(7) =

    What is the next value of i0 (= position text that is aligned with the first character of the pattern string) when KMP detects a mismatch: (5 pts)

    i0 = 0 | V 012345678901234567890 ababxabababababababab abababab

    • i0 =

    ---

  • Compute the failure function for the pattern ababcabab
    • f(0) =
    • f(1) =
    • f(2) =
    • f(3) =
    • f(4) =
    • f(5) =
    • f(6) =
    • f(7) =
    • f(8) =

    What is the next value of i0 when KMP detects a mismatch: (5 pts)

    i0 = 0 | V 012345678901234567890 ababxabababababababab ababcabab

    • i0 =

  ---

  ---

• Boyer-Moore Algorithm (20 pts)
  • Compute the lastOcc() function for the following characters for the pattern abababab (5 pts)
    • lastOcc('a') =
    • lastOcc('b') =
    • lastOcc('c') =
    • lastOcc('d') =
    • lastOcc('e') =

    What is the next value of i0 when Boyer-Moore detects a mismatch: (5 pts)

    i0 = 0 | V 012345678901234567890 ababcbababababababab abababab

    • i0 =

    ---

  • Compute the lastOcc() function for the following characters for the pattern ababcabab (5 pts)
    • lastOcc('a') =
    • lastOcc('b') =
    • lastOcc('c') =
    • lastOcc('d') =
    • lastOcc('e') =

    What is the next value of i0 when Boyer-Moore detects a mismatch: (5 pts)

    i0 = 0 | V 012345678901234567890 ababcbcababababababab ababcabab

    • i0 =

  ---

  ---

• Horspool Algorithm (20 pts)
  • Compute the lastOcc() function for the following characters for the pattern abababab (5 pts)
    • lastOcc('a') =
    • lastOcc('b') =
    • lastOcc('c') =
    • lastOcc('d') =
    • lastOcc('e') =

    What is the next value of i0 when Horspool detects a mismatch: (5 pts)

    i0 = 0 | V 012345678901234567890 ababcbababababababab abababab

    • i0 =

    ---

  • Compute the lastOcc() function for the following characters for the pattern ababcabab (5 pts)
    • lastOcc('a') =
    • lastOcc('b') =
    • lastOcc('c') =
    • lastOcc('d') =
    • lastOcc('e') =

    What is the next value of i0 when Horspool detects a mismatch: (5 pts)

    i0 = 0 | V 012345678901234567890 ababcbcababababababab ababcabab

    • i0 =

  ---

  ---

• Standard trie (20 pts)
  • Give the standard trie for the set of words S = { "bear", "beer", "bee", "be", "beef" } (10 pts)

  • Give the standard trie for all suffixes of the text "bamba" (10 pts)

  ---

  ---

• Compressed trie (20 pts)
  • Give the compressed trie for the set of words S = { "bear", "beer", "bee", "be", "beef" } (10 pts)

  • Give the compressed trie for all suffixes of the text "bamba" (10 pts)