...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Theoretical computer science >Efficient computation of maximal anti-exponent in palindrome-free strings
【24h】

Efficient computation of maximal anti-exponent in palindrome-free strings

机译：无回文字符串中最大反指数的高效计算

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

A palindrome is a string x = a(1) ... a(n) which is equal to its reversal (x) over tilde = a(n) ...a(1). We consider gapped palindromes which are strings of the form uv (u) over tilde, where u, v are strings, vertical bar v vertical bar >= 2, and (u) over tilde is the reversal of u. Replicating the standard notion of string exponent, we define the anti-exponent of a gapped palindrome uv (u) over tilde as the quotient of vertical bar uv (u) over tilde vertical bar by vertical bar uv vertical bar. To get an efficient computation of maximal anti-exponent of factors in a palindrome-free string, we apply techniques based on the suffix automaton and the reversed Lempel-Ziv factorisation. Our algorithm runs in O(n) time on a fixed-size alphabet or O (n log sigma) on a large alphabet, which dramatically outperforms the naive cubic-time solution. (C) 2016 Elsevier B.V. All rights reserved.
机译：回文是一个字符串x = a（1）... a（n），它等于在代字号= a（n）... a（1）上的反转（x）。我们考虑间隙回文，它们是在波浪号上的uv（u）形式的字符串，其中u，v是字符串，垂直条v垂直条> = 2，在波浪号上的（u）是u的反转。复制字符串指数的标准概念，我们将代字号上的空白回文uv（u）的反指数定义为代号上的竖线uv（u）乘以竖线uv竖线。为了获得无回文字符串中因子的最大反指数的有效计算，我们应用了基于后缀自动机和反向Lempel-Ziv因子分解的技术。我们的算法在固定大小的字母上以O（n）时间运行，在大型字母上以O（n log sigma）运行，这大大优于幼稚的立方时间解。 （C）2016 Elsevier B.V.保留所有权利。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号