Fundamentals of Stringology III: Suffix Tress and Suffix Arrays
summary
Defines suffix trees and suffix arrays, shows exact claims and constructions: suffix trees admit linear-time construction and let pattern queries and all-occurrence reporting run in time proportional to the pattern plus output; longest common substring and Lempel–Ziv parsing become linear after building the tree. Explains space tradeoff (suffix arrays are ~5× smaller), and presents the DC3/KS 2003-style trick: recurse on positions 1,2 mod 3, build zero-mod-3 order in linear time, then merge with at most three-character checks, yielding a linear-time suffix array and how suffix array + LCP reconstructs the suffix tree.
AI-written summary · about
chapters (7)
- 0:00Start
- 11:57Suffix Trees can be build in Linear time
- 26:02The Algorithm
- 34:54Suffix Arrays
- 40:08Algorithms using SA, and building SA
- 41:15SA in linear time and one added array
- 49:12The GSA for the second set is easy to find
related talks
24mString Comparison in Real Life
30mMarking Sense of Hierarchical Log Data
54mDesign Patterns vs Anti pattern in APL
02mTamara Kolda, Distinguished Member of Technical Staff, Sandia National Laboratories @ MLconf SF Part
44mScalable Algorithmic Primitives for Data Science
57mData, and when not to use it
25mAn Array-Oriented Language via the Design Recipe
24mHighlights from Current Programs part 2: