Parallel partial suffix array construction.Our divide and conquer suffix array construction algorithm starts by partitioning the dataset into \(K\) different "splits" with SA-IS run over independently on each split in parallel. This algorithm still requires \(O(N)\) work but runs in \(O(N/K)\) wall-clock time. This gives us \(N\) separate suffix arrays \(\mathcal{A}^{i}\).