Simple Linear Work Suffix Array Construction中提出的skew suffix array algorithm问题
question of skew suffix array algorithm presented in Simple Linear Work Suffix Array Construction
文末'Simple Linear Work Suffix Array Construction'附上源码,这部分看不懂,
// generate positions of mod 1 and mod 2 suffixes
// the "+(n0-n1)" adds a dummy mod 1 suffix if n%3 == 1
for (int i=0, j=0; i < n+(n0-n1); i++) if (i%3 != 0) s12[j++] = i;
// lsb radix sort the mod 1 and mod 2 triples
radixPass(s12 , SA12, s+2, n02, K);
radixPass(SA12, s12 , s+1, n02, K);
radixPass(s12 , SA12, s , n02, K);
第一个for循环用于获取mod1和mod2在数组中的索引;但是为什么第一个radixPass的输入索引应该是s+2呢? +2偏移量是怎么推导出来的?
写完论文我知道答案了,这三行是用来对mod1和mod2的索引从lsb到msb进行基数排序的。
文末'Simple Linear Work Suffix Array Construction'附上源码,这部分看不懂,
// generate positions of mod 1 and mod 2 suffixes
// the "+(n0-n1)" adds a dummy mod 1 suffix if n%3 == 1
for (int i=0, j=0; i < n+(n0-n1); i++) if (i%3 != 0) s12[j++] = i;
// lsb radix sort the mod 1 and mod 2 triples
radixPass(s12 , SA12, s+2, n02, K);
radixPass(SA12, s12 , s+1, n02, K);
radixPass(s12 , SA12, s , n02, K);
第一个for循环用于获取mod1和mod2在数组中的索引;但是为什么第一个radixPass的输入索引应该是s+2呢? +2偏移量是怎么推导出来的?
写完论文我知道答案了,这三行是用来对mod1和mod2的索引从lsb到msb进行基数排序的。