Week #09 | |

Pedro Ribeiro - DCC/FCUP |

*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.

- I know the

**Videos from previous edition of TAA course:**

**KMP Algorithm**- My slides from Algorithms Class (slides 6 to 16)
- KMP Algorithm for Pattern Searching (GeeksforGeeks)
- Introduction to String Matching Algorithms (TopCoder)
- Visualizing String Matching Algorithms (justinj)
- Prefix function. Knuth–Morris–Pratt algorithm (E-Maxx Algorithms in English)
- Other implementations: Stanford Notebook (secção 6.6) | Code Library
**Prefix Trees/Tries**- My slides from Algorithms Class (slides 25 to 28)
- Trie | (Insert and Search) (GeeksforGeeks)
- Trie Visualization (Data Structure Visualizations, David Galles)
- Other implementations: Code Library
**Aho-Corasick Algorithm**- Aho-Corasick Algorithm for Pattern Searching (GeeksforGeeks)
- Aho-Corasick algorithm. Construction (CodeForces)
- Aho-Corasick – implementation and animation (Algorithms and Stuff - IvanK)
- Aho-Corasick algorithm (E-Maxx Algorithms in English)
- Other implementations: Code Library
**Suffix Trees/Suffix arrays**- My slides from Algorithms Class (slides 29 to 40)
- Visualization of Suffix Trees (VisuAlgo)
- Visualization of Suffix Arrays (VisuAlgo)
- Pattern Searching using Suffix Tree (GeeksforGeeks)
- Suffix Array | Set 1 (Introduction) (GeeksforGeeks)
- Suffix arrays – a programming contest approach (Stanford, A. Vladu and C. Negruseri)
- Suffix Array (E-Maxx Algorithms in English)

- SPOJ NHAY - A Needle in the Haystack (testing KMP)
- SPOJ ARDA1 - The hunt for Gollum (2D KMP/Aho-Corasick or Baker-Bird Algorithm)
- SPOJ PSTRING - Remove The String (KMP + DP)

Pedro Ribeiro - DCC/FCUP |
**Último update:**