Sample Video Frame

Created by Zed A. Shaw Updated 2024-02-17 04:54:36

Exercise 22: Suffix Arrays

I'd like to tell you a story about suffix arrays. I was interviewing at a company in Seattle during a time I was curious about how to most efficiently create a diff on an executable binary. My research brought me to the algorithms Suffix Array and Suffix Tree. The Suffix Array is simply where you sort all the suffixes of a string into a sorted list. The Suffix Tree is similar but done more like a BSTree than a list. These algorithms were fairly simple and had fast performance once you did the sorting operation. The problem they solved was finding the longest common substring between two strings (or in this case, lists of bytes).

You can make a suffix array in Python really easily:

Previous Lesson Next Lesson

Register for Learn More Python the Hard Way

Register today for the course and get the all currently available videos and lessons, plus all future modules for no extra charge.