2 citations · 6 across the 31 of their papers we have counts for
8 papers · 1 filter
Space-Efficient Online Computation of String Net Occurrences
Takuya Mieno, Shunsuke Inenaga
A substring of a string is said to be a repeat if occurs at least twice in . An occurrence of a repeat in is said to be a net occurrence if each of…
Data Structures for Range Sorted Consecutive Occurrence Queries
Waseem Akram, Takuya Mieno
The string indexing problem is a fundamental computational problem with numerous applications, including information retrieval and bioinformatics. It aims to efficiently solve the…
Online and Offline Algorithms for Counting Distinct Closed Factors via Sliding Suffix Trees
Takuya Mieno, Shun Takahashi, Kazuhisa Seto +1
A string is said to be closed if its length is one, or if it has a non-empty factor that occurs both as a prefix and as a suffix of the string, but does not occur elsewhere. The no…
Faster and simpler online/sliding rightmost Lempel-Ziv factorizations
Wataru Sumiyoshi, Takuya Mieno, Shunsuke Inenaga
We tackle the problems of computing the rightmost variant of the Lempel-Ziv factorizations in the online/sliding model. Previous best bounds for this problem are O(n log n) time wi…
Subsequence Matching and LCS with Segment Number Constraints
Yuki Yonemoto, Takuya Mieno, Shunsuke Inenaga +2
The longest common subsequence (LCS) is a fundamental problem in string processing which has numerous algorithmic studies, extensions, and applications. A sequence $u_1, \ldots, u_…
Subsequence Matching and LCS under Cartesian-Tree Equivalence
Taketo Tsujimoto, Yuki Yonemoto, Hiroki Shibata +3
Two strings of the same length are said to Cartesian-tree match (CT-match) if their Cartesian-trees are isomorphic [Park et al., TCS 2020]. Cartesian-tree matching is a natural mod…
Computing Minimal Absent Words and Extended Bispecial Factors with CDAWG Space
Shunsuke Inenaga, Takuya Mieno, Hiroki Arimura +2
A string is said to be a minimal absent word (MAW) for a string if does not occur in and any proper substring of occurs in . We focus on non-trivial MAWs whi…
Shortest cover after edit
Kazuki Mitani, Takuya Mieno, Kazuhisa Seto +1
This paper investigates the (quasi-)periodicity of a string when the string is edited. A string is called a cover (as known as a quasi-period) of a string if each character…