106 citations · 239 across the 67 of their papers we have counts for
6 papers · 1 filter
Space Efficient Linear Time Lempel-Ziv Factorization on Constant~Size~Alphabets
Keisuke Goto, Hideo Bannai
We present a new algorithm for computing the Lempel-Ziv Factorization (LZ77) of a given string of length in linear time, that utilizes only bits of working spa…
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…
On the existence of tight relative 2-designs on binary Hamming association schemes
Eiichi Bannai, Etsuko Bannai, Hideo Bannai
It is known that there is a close analogy between "Euclidean t-designs vs. spherical t-designs" and "Relative t-designs in binary Hamming association schemes vs. combinatorial t-de…
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…