Shortest Unique Substrings Queries in Optimal Time
Shortest Unique Substrings Queries in Optimal Time
复制标题
最优时间最短唯一子串查询
DOI：
10.1007/978-3-319-04298-5_44
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
and Masayuki Takeda
中科院分区：
文献类型：
--
作者：
Kazuya Tsuruta;Shunsuke Inenaga;Hideo Bannai;and Masayuki Takeda
我们提出了一个最短唯一子串问题的最优线性时间算法，从而改进了Pei等人的算法（ICDE 2013）。我们的实现很简单，基于后缀数组。计算实验表明，我们的算法是更有效的在实践中，相比，裴等人。
We present an optimal, linear time algorithm for the shortest unique substring problem, thus improving the algorithm by Pei et al. (ICDE 2013). Our implementation is simple and based on suffix arrays. Computational experiments show that our algorithm is much more efficient in practice, compared to that of Pei et al.