...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>LIPIcs : Leibniz International Proceedings in Informatics >Computing longest common square subsequences
【24h】

Computing longest common square subsequences

机译：计算最长的公共平方子序列

获取原文
   

获取外文期刊封面封底 >>

       
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

A square is a non-empty string of form YY. The longest common square subsequence (LCSqS) problem is to compute a longest square occurring as a subsequence in two given strings A and B. We show that the problem can easily be solved in O(n^6) time or O(|M|n^4) time with O(n^4) space, where n is the length of the strings and M is the set of matching points between A and B. Then, we show that the problem can also be solved in O(sigma |M|^3 + n) time and O(|M|^2 + n) space, or in O(|M|^3 log^2 n log log n + n) time with O(|M|^3 + n) space, where sigma is the number of distinct characters occurring in A and B. We also study lower bounds for the LCSqS problem for two or more strings.
机译：正方形是形式为YY的非空字符串。最长公共平方子序列（LCSqS）问题是计算在两个给定的字符串A和B中作为子序列出现的最长平方。我们证明了可以在O（n ^ 6）时间或O（| M | n ^ 4）时间与O（n ^ 4）空间，其中n是字符串的长度，M是A和B之间的匹配点的集合。然后，我们证明了问题也可以在O（sigma）中解决| M | ^ 3 + n）时间和O（| M | ^ 2 + n）空间，或在O（| M | ^ 3 log ^ 2 n log log n + n）时间中加上O（| M | ^ 3 + n）空间，其中sigma是在A和B中出现的不同字符的数量。我们还研究了两个或更多字符串的LCSqS问题的下界。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号