|
|
|
|
|
Shiori Mitsuya, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda
We consider the communication complexity of the Hamming distance of two strings. Bille et al. [SPIRE 2018] considered the communication complexity of the longest common prefix (LCP) problem in the setting where the two parties have their strings in a com...
ver más
|
|
|
|
|
|
|
|
|
|
|
Hideo Bannai, Travis Gagie, Gary Hoppenworth, Simon J. Puglisi and Luís M. S. Russo
We extend recent results regarding finding shortest unique substrings (SUSs) to obtain new time-space tradeoffs for this problem and the generalization of finding k-mismatch SUSs. Our new results include the first algorithm for finding a k-mismatch SUS i...
ver más
|
|
|
|
|
|
|
|
|
|
|
Isamu Furuya, Takuya Takagi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai and Takuya Kida
This study presents an analysis of RePair, which is a grammar compression algorithm known for its simple scheme, while also being practically effective. First, we show that the main process of RePair, that is, the step by step substitution of the most fr...
ver más
|
|
|
|
|
|