We present the first worst-case linear time algorithm that directly computes the parameterized suffix and lcparrays for constant sized alphabets. Previous algorithms either required quadratic time or the parameterize...
详细信息
ISBN:
(纸本)9783030326852;9783030326869
We present the first worst-case linear time algorithm that directly computes the parameterized suffix and lcparrays for constant sized alphabets. Previous algorithms either required quadratic time or the parameterized suffix tree to be built first. More formally, for a string over static alphabet Sigma and parameterized alphabet Pi, our algorithm runs in O(n pi) time and O(n) words of space, where pi is the number of distinct symbols of Pi in the string.
暂无评论