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.