Last update: September 25, 2022  ce205 From: ref_link

CE205 Data Structures

Week-12

String Search Algorithms, Tries, Data Structures for Disjoint Sets

Download DOC, SLIDE, PPTX

---

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%E2%80%93Morris%E2%80%93Pratt_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%E2%80%93Moore%E2%80%93Horspool_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%E2%80%93Moore_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

---

\[ End-Of-Week-12 \]

---

Last update: September 25, 2022
Created: December 29, 2021

Contributors:
• Ugur Coruh (100.0%)