Arrow Research search

Author name cluster

Wataru Matsubara

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

2 papers
2 author rows

Possible papers

2

MFCS Conference 2013 Conference Paper

Detecting Regularities on Grammar-Compressed Strings

  • Tomohiro I
  • Wataru Matsubara
  • Kouji Shimohira
  • Shunsuke Inenaga
  • Hideo Bannai
  • Masayuki Takeda
  • Kazuyuki Narisawa
  • Ayumi Shinohara

Abstract We solve the problems of detecting and counting various forms of regularities in a string represented as a Straight Line Program (SLP). Given an SLP of size n that represents a string s of length N, our algorithm computes all runs and squares in s in O ( n 3 h ) time and O ( n 2 ) space, where h is the height of the derivation tree of the SLP. We also show an algorithm to compute all gapped-palindromes in O ( n 3 h + gnh log N ) time and O ( n 2 ) space, where g is the length of the gap. The key technique of the above solution also allows us to compute the periods and covers of the string in O ( n 2 h ) time and O ( nh ( n + log 2 N )) time, respectively.

Details

TCS Journal 2009 Journal Article

Efficient algorithms to compute compressed longest common substrings and compressed palindromes

  • Wataru Matsubara
  • Shunsuke Inenaga
  • Akira Ishino
  • Ayumi Shinohara
  • Tomoyuki Nakamura
  • Kazuo Hashimoto

This paper studies two problems on compressed strings described in terms of straight line programs (SLPs). One is to compute the length of the longest common substring of two given SLP-compressed strings, and the other is to compute all palindromes of a given SLP-compressed string. In order to solve these problems efficiently (in polynomial time w. r. t. the compressed size) decompression is never feasible, since the decompressed size can be exponentially large. We develop combinatorial algorithms that solve these problems in O ( n 4 log n ) time with O ( n 3 ) space, and in O ( n 4 ) time with O ( n 2 ) space, respectively, where n is the size of the input SLP-compressed strings.

Details DOI