Suffix Tree

Below is a series of videos from the lectures that I gave on suffix trees for the module “Text Search and Processing” in King’s College London (Feb 2017 and 2018).

L1: Suffix Tree – In the context of pattern matching

This part of the lecture deals with various static settings of the pattern matching problem so as to introduce and illustrate the context in which suffix trees are used.

L2: Suffix Trie – Introduction

This part of the lecture introduces the suffix trie and some of its basic applications that make understanding the suffix tree easier.

L3: Suffix Trie – Analysis of Size

This part of the lecture deals with the analysis of the size of a suffix trie.

L4: SuffixTree – Construction

This part of the lecture covers the construction of a suffix tree using three methods – compaction of a suffix trie, brute force method, and McCreight’s Algorithm.

L5: Suffix Tree – Analysis of McCreight’s Algorithm

This part of the lecture deals with the analysis of the running time for construction of a suffix tree using McCreight’s algorithm.

L6: SuffixTree – Applications

This part of the lecture explores some of the important applications of a suffix tree and introduces the notion of a generalised suffix tree.