Aula #07
	Pedro Ribeiro - DCC/FCUP

Principais conceitos abordados na aula

1. String Matching:
   • Percebo o algoritmo de Knuth-Morris-Pratt (KMP), como pode ser usado para fazer string matching em tempo linear e compreendo o que guarda a sua "failure function".
   • Percebo o conceito de uma árvore de prefixos (trie).
   • Percebo o algoritmo de Aho-Corasick e a maneira como generaliza o KMP para múltiplas strings.
   • Percebo o conceito de suffix trees e o tipo de problemas que podem resolver.
   • Percebo o conceito de suffix arrays e como podem ser usadas para resolver os "mesmos" problemas que uma suffix tree, mas usando muito menos memória.

Material de Estudo

Principais referências

• Algoritmo KMP
• Slides meus de Algoritmos (slides 6 a 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)
• Outras implementações: Stanford Notebook (secção 6.6) | Code Library
• Árvore de Prefixos/Trie
• Slides meus de Algoritmos (slides 25 a 28)
• Trie | (Insert and Search) (GeeksforGeeks)
• Trie Visualization (Data Structure Visualizations, David Galles)
• Outras implementações: Code Library
• Algoritmo Aho-Corasick
• 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)
• Outras implementações: Code Library
• Suffix Trees/Suffix arrays
• Slides meus de Algoritmos (slides 29 a 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)

Problemas de Iniciação/Reforço

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

Pedro Ribeiro - DCC/FCUP | Último update: