Swift Algorithm Club: Boyer Moore String Search Algorithm

Matching

Another component of the Boyer Moore algorithm is backwards string matching. You’ll devise a method to handle that. This method has 3 goals:

1. Backwards match 2 strings character by character.
2. If at any point the match fails, the method will return nil.
3. If a match completes successfully, return the String.Index of the source string that matches the first letter of the pattern.

Write the following beneath skipTable:

// 1
fileprivate func match(from currentIndex: Index, with pattern: String) -> Index? {
  // more to come

  // 2
  return match(from: index(before: currentIndex), with: "\(pattern.dropLast())")
}

This is the recursive method you’ll use to do matching against the source and pattern strings:

1. currentIndex keeps track of the current character of the source string you want to match against.
2. On each recursive call, you decrement the index, and shorten the pattern string by dropping its last character.

The behaviour of this method looks like this:

Now, it’s time to deal with the comparison logic. Update the match method to the following:

fileprivate func match(from currentIndex: Index, with pattern: String) -> Index? {
  // 1
  if currentIndex < startIndex { return nil }
  if currentIndex >= endIndex { return nil }
  
  // 2
  if self[currentIndex] != pattern.last { return nil }

  // 3
  if pattern.count == 1 && self[currentIndex] == pattern.last { return currentIndex }
  return match(from: index(before: currentIndex), with: "\(pattern.dropLast())")
}

1. You’ll need to do some bounds checking. If currentIndex ever goes out of bounds, you’ll return nil
2. If the characters don’t match, then there’s no point to continue further.
3. If the final character in pattern matches, then you’ll return the current index, indicating a match was made at starting at this location.

guard currentIndex >= startIndex && currentIndex < endIndex && pattern.last == self[currentIndex] 
  else { return nil }
if pattern.count == 1 && self[currentIndex] == pattern.first { return currentIndex }

guard currentIndex >= startIndex && currentIndex < endIndex && pattern.last == self[currentIndex] 
  else { return nil }
if pattern.count == 1 && self[currentIndex] == pattern.first { return currentIndex }

With the skip table and matching function ready, it's time to tackle the final piece of the puzzle!

index(of:)

Update the index method to the following:

func index(of pattern: String) -> Index? {
  // 1
  let patternLength = pattern.count
  guard patternLength > 0, patternLength <= count else { return nil }

  // 2
  let skipTable = pattern.skipTable
  let lastChar = pattern.last!

  // 3
  var i = index(startIndex, offsetBy: patternLength - 1)
  
  // more to come...
  return nil
}

You've set up the playing field:

1. First, check to see if the length of the pattern string is within the bounds of the source string.
2. Keep track of the skip table for the pattern string, and it's last character.
3. You'll initialize a String.Index to keep track of traversals. Since you're planning on matching the strings backwards, you can have a small headstart by offsetting this index by the length of the pattern.

Next, you'll define the logic for the matching and traversals. Add the following just before the return statement:

// 1
while i < endIndex {
  let c = self[i]

  // 2
  if c == lastChar {
    if let k = match(from: i, with: pattern) { return k }
    i = index(after: i)
  } else { 
    // 3
    i = index(i, offsetBy: skipTable[c] ?? patternLength, limitedBy: endIndex) ?? endIndex
  }
}

Here's the play by play:

1. You'll continue to traverse the source string until you reach the endIndex
2. If the current character of the source string matches the last character of the pattern string, you'll attempt to run the match function. If this returns a non nil value, it means you've found a match, so you'll return the index that matches the pattern. Otherwise, you'll move to the next index.
3. If you can't make a match, you'll consult the skip table to see how many indexes you can skip. If this skip goes beyond the length of the source string, you'll just head straight to the end.

Time to give it a whirl. Add the following at the bottom of the playground:

let sourceString = "Hello World!"
let pattern = "World"
sourceString.index(of: pattern)

You should get a 6 for the index. Woohoo, it's working!

Where to go From Here?

I hope you enjoyed this tutorial on efficient string searching!

Here is a playground with the above code. You can also find the original implementation and further discussion on the repo for Brute Force String Search and Boyer Moore String Search.

This was just one of the many algorithms in the Swift Algorithm Club repository. If you're interested in more, check out the repo.

It's in your best interest to know about algorithms and data structures - they're solutions to many real-world problems, and are frequently asked as interview questions. Plus it's fun!

So stay tuned for many more tutorials from the Swift Algorithm club in the future. In the meantime, if you have any questions on implementing trees in Swift, please join the forum discussion below.

If you enjoyed what you learned in this tutorial, why not check out our Data Structures and Algorithms in Swift book, available on our store?

In Data Structures and Algorithms in Swift, you’ll learn how to implement the most popular and useful data structures and when and why you should use one particular datastructure or algorithm over another. This set of basic data structures and algorithms will serve as an excellent foundation for building more complex and special-purpose constructs.

As well, the high-level expressiveness of Swift makes it an ideal choice for learning these core concepts without sacrificing performance.

• You’ll start with the fundamental structures of linked lists, queues and stacks, and see how to implement them in a highly Swift-like way.
• Move on to working with various types of trees, including general purpose trees, binary trees, AVL trees, binary search trees and tries.
• Go beyond bubble and insertion sort with better-performing algorithms, including mergesort, radix sort, heap sort and quicksort.
• Learn how to construct directed, non-directed and weighted graphs to represent many real-world models, and traverse graphs and trees efficiently with breadth-first, depth-first, Dijkstra’s and Prim’s algorithms to solve problems such as finding the shortest path or lowest cost in a network.
• And much, much more!

By the end of this book, you’ll have hands-on experience solving common issues with data structures and algorithms — and you’ll be well on your way to developing your own efficient and useful implementations.