Parallel merge of partial suffix arrays.We now merge these separate arrays together into a single suffix array \(\mathcal{A}\), Consider the simpler case of two partial suffix arrays \(B\) and \(C\) that we would like to merge together. We can achieve this by letting \(i=0\) index \(B\) and \(j=0\) index \(C\). Each iteration of the algorithm then pushes \(B_{i}\) into \(\mathcal{A}\) if \(S_{B_{i\cdots}}<S_{C_{i}}\) and \(C_{i}\) otherwise, repeating until \(i=|B|-1\) and \(j=|C|-1\). To generalize to \(K\) splits, we need only replace the single comparison above with a min-heap requiring \(O(\log K)\ll 10\) work on each iteration.
부분 접미사 배열의 병렬 병합. 이제 이러한 개별 배열을 단일 접미사 배열 \(\mathcal{A}\)로 병합합니다. 병합하려는 두 개의 부분 접미사 배열 \(B\)와 \(C\)의 더 간단한 경우를 생각해 보겠습니다. \(i=0\) 인덱스 \(B\)와 \(j=0\) 인덱스 \(C\)를 사용하면 이를 달성할 수 있습니다. 그러면 알고리즘의 각 반복은 \(S_{B_{i\cdots}}<S_{C_{i}}\)이면 \(B_{i}\)를 \(\mathcal{A}\)로 밀어넣고, 그렇지 않으면 \(C_{i}\)를 반복하여 \(i=|B|-1\) 및 \(j=|C|-1\)이 될 때까지 반복합니다. \(K\)개의 분할로 일반화하려면 위의 단일 비교를 각 반복에서 \(O(\log K)\ll 10\) 작업이 필요한 min-heap으로 대체하면 됩니다.
부분 접미사 배열의 병렬 병합. 이제 이러한 개별 배열을 단일 접미사 배열 \(\mathcal{A}\)로 병합합니다. 병합하려는 두 개의 부분 접미사 배열 \(B\)와 \(C\)의 더 간단한 경우를 생각해 보겠습니다. i=0$ 인덱스 \(B\)와 \(j=0$ 인덱스 \(C\)를 사용하면 이를 달성할 수 있습니다. 그러면 알고리즘의 각 반복은 \(S_{B_{i\cdots}}<S_{C_{i}}\)이면 \(B_{i}\)를 \(\mathcal{A}\)로 밀어넣고, 그렇지 않으면 \(C_{i}\)를 반복하여 \(i=|B|-1\) 및 \(j=|C|-1\)이 될 때까지 반복합니다. K개의 분할로 일반화하려면 위의 단일 비교를 각 반복에서 \(O(\log K)\ll 10\) 작업이 필요한 최소 힙으로 대체하면 됩니다.