tag

#dc3

3 pages tagged

Wiki › Algorithms › 01. Searching and Sorting › 8. Integer and Distribution Sorting ›

DC3 Suffix Array Sort

DC3 Suffix Array Sort DC3 suffix array sort is the concrete formulation of the skew algorithm based on a difference cover modulo 3. It builds the suffix array in linear time by sorting a subset of suffixes, assigning them ranks, and merging with the remaining suffixes. It is widely used in high-performance string processing systems. Problem Given a string $S$ of length $n$, construct the suffix array: $$ SA =...
algorithms sorting string-processing suffix-array dc3
Wiki › Algorithms › 01. Searching and Sorting › 4. Tree and Indexed Search ›

DC3 Suffix Array

Skew Suffix Array Sort (DC3) DC3, also called skew algorithm, builds a suffix array in linear time by splitting suffix positions into residue classes modulo 3 and recursively sorting a subset. It reduces the full suffix ordering problem into a smaller problem, then merges results using rank comparisons. Problem Given a string $T$ of length $n$, construct its suffix array: $$ SA[0 \dots n-1] $$ such that all suffixes are...
algorithms sorting suffix-array dc3 string
Wiki › Algorithms › 01. Searching and Sorting › 8. Integer and Distribution Sorting ›

Skew Suffix Array Sort

Skew Suffix Array Sort Skew suffix array sort, also known as the DC3 algorithm, constructs a suffix array in linear time by recursively sorting a subset of suffixes whose positions are not divisible by 3. The remaining suffixes are then merged using the already computed order. Problem Given a string $S$ of length $n$, construct its suffix array: $$ SA = \text{sorted indices of all suffixes of } S $$...
algorithms sorting string-processing suffix-array dc3