106 citations · 249 across the 101 of their papers we have counts for
4 papers · 1 filter
Faster Compact On-Line Lempel-Ziv Factorization
Jun'ichi Yamamoto, Tomohiro I, Hideo Bannai +2
We present a new on-line algorithm for computing the Lempel-Ziv factorization of a string that runs in time and uses only bits of working space, where …
Detecting regularities on grammar-compressed strings
Tomohiro I, Wataru Matsubara, Kouji Shimohira +5
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 that represents a s…
Efficient Lyndon factorization of grammar compressed text
Tomohiro I, Yuto Nakashima, Shunsuke Inenaga +2
We present an algorithm for computing the Lyndon factorization of a string that is given in grammar compressed form, namely, a Straight Line Program (SLP). The algorithm runs in $O…
Computing convolution on grammar-compressed text
Toshiya Tanaka, Tomohiro I, Shunsuke Inenaga +2
The convolution between a text string of length and a pattern string of length can be computed in time by FFT. It is known that various types of appro…