2 citations · 2 across the 4 of their papers we have counts for
15 papers
The Parameterized Periodicity Lemma
Rikuya Hamai, Yuto Nakashima, Shunsuke Inenaga
Fine and Wilf [Proc. Amer. Math. Soc. 1965] showed that any string of length at least with periods and also has period . For parameterized strings, Apo…
Compact Enumeration of Maximal Closed Substrings in Run-Length Encoded Strings
Haruki Umezaki, Hiroki Shibata, Yuto Nakashima +1
A string is closed if , or if has a non-empty proper border occurring only as its prefix and suffix. A maximal closed substring (MCS) is a maximal occurrence of a cl…
Online computation of maximal closed substrings
Hiroki Shibata, Haruki Umezaki, Takuya Mieno +2
A non-empty string is closed if it has length one or its longest border appears exactly twice in the string. An occurrence of a closed substring is a maximal closed substring (MCS)…
Grammar Index By Induced Suffix Sorting
Tooru Akagi, Dominik Köppl, Yuto Nakashima +3
Pattern matching is the most central task for text indices. Most recent indices leverage compression techniques to make pattern matching feasible for massive but highly-compressibl…
Counting Distinct (Non-)Crossing Substrings in Optimal Time
Haruki Umezaki, Hiroki Shibata, Dominik Köppl +3
Let be a string of length . The problem of counting factors crossing a position -- Problem 64 from the textbook ``125 Problems in Text Algorithms'' [Crochemore, Lecroq, and…
Sensitivity of Repetitiveness Measures to String Reversal
Hideo Bannai, Yuto Fujie, Peaker Guo +4
We study the impact that string reversal can have on several repetitiveness measures. First, we exhibit an infinite family of strings where the number, , of runs in the run-leng…