Outline

• Strings
  • Reverse Factor Algorithm (String Search)
    • Knuth-Morris-Pratt Algorithm
    • Horspool Algorithm
    • Boyer-Moore Algorithm
    • Brute-Force / Linear Text Search
    • DFA Text Search
  • Tries
    • Patricia Tree (Radix Tree)
  • Data Structures for Disjoint Sets
    • Disjoint-set operations
    • Linked-list representation of disjoint sets
    • Disjoint-set forests
    • Analysis of union by rank with path compression

Strings - Reverse Factor Algorithm (String Search)

Knuth-Morris-Pratt Algorithm

• https://en.wikipedia.org/wiki/Knuth–Morris–Pratt_algorithm
• https://www.geeksforgeeks.org/kmp-algorithm-for-pattern-searching/
• https://www.javatpoint.com/daa-knuth-morris-pratt-algorithm
• https://www.educative.io/answers/what-is-the-knuth-morris-pratt-algorithm
• http://www.btechsmartclass.com/data_structures/knuth-morris-pratt-algorithm.html
• https://www-igm.univ-mlv.fr/~lecroq/string/node32.html#SECTION00320
• https://algs4.cs.princeton.edu/lectures/keynote/53SubstringSearch.pdf

Strings - Reverse Factor Algorithm (String Search)

Horspool Algorithm

• https://en.wikipedia.org/wiki/Boyer–Moore–Horspool_algorithm
• https://www.inf.hs-flensburg.de/lang/algorithmen/pattern/horsen.htm
• https://www-igm.univ-mlv.fr/~lecroq/string/node18.html

Strings - Reverse Factor Algorithm (String Search)

Boyer-Moore Algorithm

• https://en.wikipedia.org/wiki/Boyer–Moore_string-search_algorithm
• https://www.geeksforgeeks.org/boyer-moore-algorithm-for-pattern-searching/?ref=gcse

Strings - Reverse Factor Algorithm (String Search)

Brute-Force / Linear Text Search

• https://algs4.cs.princeton.edu/lectures/keynote/53SubstringSearch.pdf

Strings - Reverse Factor Algorithm (String Search)

DFA (deterministic finite automaton) Text Search

• https://www.geeksforgeeks.org/finite-automata-algorithm-for-pattern-searching/

Tries

Patricia Tree (Radix Tree)

• https://en.wikipedia.org/wiki/Radix_tree
• http://www.btechsmartclass.com/data_structures/tries.html
• https://www.geeksforgeeks.org/implementing-patricia-trie-in-java/

Data Structures for Disjoint Sets

• https://ucoruh.github.io/ce100-algorithms-and-programming-II/week-10/ce100-week-10-graphs/?h=disjoint#disjoint-set-operations

• Disjoint-set operations

• Linked-list representation of disjoint sets

• Disjoint-set forests

• Analysis of union by rank with path compression

• https://www.geeksforgeeks.org/disjoint-set-data-structures/

• https://www.javatpoint.com/disjoint-set-data-structure