LeetCode 1062: Longest Repeating Substring
A clear explanation of finding the longest substring that appears at least twice using binary search on length with rolling hash.
Tag
Suffix-Array
15 notes
LeetCode 1044: Longest Duplicate Substring
A clear explanation of finding the longest duplicate substring using binary search on length combined with Rabin-Karp rolling hash.
Suffix Array Radix Sort
Construct a suffix array by sorting rank pairs with radix or counting sort during the doubling method.
DC7 Suffix Array Sort
Difference cover modulo 7 suffix array construction method that generalizes DC3 with a larger recursive sample.
DC3 Suffix Array Sort
Difference cover modulo 3 algorithm for linear-time suffix array construction using radix sorting and merging.
Skew Suffix Array Sort
Linear-time suffix array construction using the DC3 algorithm that recursively sorts positions modulo 3.
SA IS
Linear-time suffix array construction algorithm based on induced sorting of LMS suffixes.
Induced Sorting
Linear-time technique for suffix array construction that induces order of suffixes from a subset of sorted suffixes.
Suffix Array Doubling Sort
Construct a suffix array by iteratively sorting suffixes using doubling technique with rank pairs.
SA-IS Suffix Array Construction
Linear time suffix array construction using induced sorting of LMS substrings.
DC7 Suffix Array Sort
Generalized divide and conquer suffix array construction using modulo 7 partitioning.
Skew Suffix Array Sort (DC3)
Linear time suffix array construction using the DC3 divide and conquer strategy.
Suffix Array Doubling Sort
Build a suffix array using the prefix doubling technique with iterative ranking.
LCP Accelerated Suffix Search
Search for a pattern in a suffix array using LCP information to reduce redundant character comparisons.
Suffix Array Binary Search
Search for a pattern in a text by binary searching the lexicographically sorted suffix array.