论文标题
最长的串联分散子序列
Small Longest Tandem Scattered Subsequences
论文作者
论文摘要
我们考虑识别字符串中串联分散子序列的问题。我们的算法标识了最长的子序列，该子序列发生两次，而在字符串中没有重叠。该算法基于亨特 - 兹曼斯基算法，因此，如果字符串不相似，则其性能会提高。这自然发生在大型字母上的字符串上。我们的算法依赖于支持动态最长增加子序列的数据结构的新结果。在此过程中，我们还获得了减少字符串比较问题的改进算法。
We consider the problem of identifying tandem scattered subsequences within a string. Our algorithm identifies a longest subsequence which occurs twice without overlap in a string. This algorithm is based on the Hunt-Szymanski algorithm, therefore its performance improves if the string is not self similar. This occurs naturally on strings over large alphabets. Our algorithm relies on new results for data structures that support dynamic longest increasing sub-sequences. In the process we also obtain improved algorithms for the decremental string comparison problem.
