常数工作空间并行构造后缀数组的方法及系统

摘要

本发明公开了常数工作空间并行构造后缀数组的方法及系统，通过获取字符串X中所有LMS子串的首字符指针并记录在数组P1中，以进一步利用P1和SA来对字符串X中所有的LMS子串进行常数工作空间内的并行归纳排序，得到字符串X1，并依据X1中字符的唯一性来区别SA的不同构造输入参数，最终通过X1与其后缀数组SA1的对应关系得以在常数工作空间内并行归纳计算字符串X的后缀数组到SA中。本发明降低了计算机内存要求且运行速度更快，使时空复杂度达到最优，适用于大规模字符串的后缀数组构建。