首页    期刊浏览 2024年07月18日 星期四
登录注册

文章基本信息

  • 标题:An Efficient Algorithm to Test Square-Freeness of Strings Compressed by Balanced Straight Line Programs
  • 本地全文:下载
  • 作者:Wataru Matsubara ; Shunsuke Inenaga ; Ayumi Shinohara.
  • 期刊名称:Chicago Journal of Theoretical Computer Science
  • 印刷版ISSN:1073-0486
  • 出版年度:2010
  • 卷号:2010
  • 出版社:MIT Press ; University of Chicago, Department of Computer Science
  • 摘要:

    In this paper we study the problem of deciding whether a given compressed string contains a square . A string x is called a square if x = zz and z = u^k implies k = 1 and u = z . A string w is said to be square-free if no substrings of w are squares. However, very little is known for testing square-freeness of a given compressed string . In this paper, we give an O( max(n^2, n log^2 N)) -time O(n^2) -space solution to test square-freeness of a given compressed string, where n and N are the size of a given compressed string and the corresponding decompressed string, respectively. Our input strings are compressed by balanced straight line program ( BSLP ). We remark that BSLP has exponential compression, that is, N = O(2^n) . Hence no decompress-then-test approaches can be better than our method in the worst case.

国家哲学社会科学文献中心版权所有