Main learning outcomes for this class
- String Matching:
- I know the Knuth-Morris-Pratt (KMP) algorithm, how it can be used to do string matching in linear time and I understand what its "failure function" stores.
- I know the concept of prefix tree (trie).
- I understand the Aho-Corasick algorithm and how it generalizes KMP for multiple strings.
- I know the concept of suffix trees and the kind of problems they can solve.
- I know the concept of suffix arrays and how they can be used to solve the "same" problems as a suffix tree, but using less memory.
Study Material
Main References
- Videos from previous edition of TAA course:
- KMP Algorithm
- Prefix Trees/Tries
- Aho-Corasick Algorithm
- Suffix Trees/Suffix arrays
Initiation/Reinforcement Problems
Pedro Ribeiro - DCC/FCUP | Last update:
