2 citations · 6 across the 31 of their papers we have counts for
28 papers · 1 filter
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)…
Online Computation of Palindromes and Suffix Trees on Tries
Hiroki Shibata, Mitsuru Funakoshi, Takuya Mieno +5
We consider the problems of computing maximal palindromes and distinct palindromes in a trie. A trie is a natural generalization of a string, which can be seen as a single-path tre…
On the number of MUSs crossing a position
Hiroto Fujimaru, Takuya Mieno, Shunsuke Inenaga
A string is said to be a minimal unique substring (MUS) of a string if occurs exactly once in , and any proper substring of occurs at least twice in . It is k…
Almost succinct representation of maximal palindromes
Takuya Mieno, Tomohiro I, Valerio Stancanelli
Palindromes are strings that read the same forward and backward. The computation of palindromic structures within strings is a fundamental problem in string algorithms, being motiv…
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…
Linear-time computation of generalized minimal absent words for multiple strings
Kouta Okabe, Takuya Mieno, Yuto Nakashima +2
A string is called a minimal absent word (MAW) for a string if does not occur as a substring in and all proper substrings of occur in . MAWs are well-studied…
Sliding suffix trees revisited
Laurentius Leonard, Shunsuke Inenaga, Hideo Bannai +1
The sliding suffix tree (Fiala \& Greene, 1989) is a suffix tree that is maintained for a sliding window of size that shifts over an input text of lengt…
Computing palindromes on a trie in linear time
Takuya Mieno, Mitsuru Funakoshi, Shunsuke Inenaga
A trie is a rooted tree such that each edge is labeled by a single character from the alphabet, and the labels of out-going edges from the same node are mutually dist…
Computing maximal palindromes in non-standard matching models
Takuya Mieno, Mitsuru Funakoshi, Yuto Nakashima +3
Palindromes are popular and important objects in textual data processing, bioinformatics, and combinatorics on words. Let be a string where and are of the same le…
Finding Top-k Longest Palindromes in Substrings
Kazuki Mitani, Takuya Mieno, Kazuhisa Seto +1
Palindromes are strings that read the same forward and backward. Problems of computing palindromic structures in strings have been studied for many years with a motivation of their…
Online algorithms for finding distinct substrings with length and multiple prefix and suffix conditions
Laurentius Leonard, Shunsuke Inenaga, Hideo Bannai +1
Let two static sequences of strings and , representing prefix and suffix conditions respectively, be given as input for preprocessing. For the query, let two positive intege…
Data structures for computing unique palindromes in static and non-static strings
Takuya Mieno, Mitsuru Funakoshi
A palindromic substring of a string is said to be a shortest unique palindromic substring (SUPS) in for an interval if is a shortest palindro…
Minimal Absent Words on Run-Length Encoded Strings
Tooru Akagi, Kouta Okabe, Takuya Mieno +2
A string is called a minimal absent word (MAW) for another string if does not occur (as a substring) in and any proper substring of occurs in . State-of-the-…
Cartesian Tree Subsequence Matching
Tsubasa Oizumi, Takeshi Kai, Takuya Mieno +2
Park et al. [TCS 2020] observed that the similarity between two (numerical) strings can be captured by the Cartesian trees: The Cartesian tree of a string is a binary tree recursiv…
On the approximation ratio of LZ-End to LZ77
Takumi Ideue, Takuya Mieno, Mitsuru Funakoshi +3
A family of Lempel-Ziv factorizations is a well-studied string structure. The LZ-End factorization is a member of the family that achieved faster extraction of any substrings (Kref…
Minimal unique palindromic substrings after single-character substitution
Mitsuru Funakoshi, Takuya Mieno
A palindrome is a string that reads the same forward and backward. A palindromic substring of a string is called a minimal unique palindromic substring (MUPS) of if …
String Sanitization Under Edit Distance: Improved and Generalized
Takuya Mieno, Solon P. Pissis, Leen Stougie +1
Let be a string of length over an alphabet , be a positive integer, and be a set of length- substrings of . The ETFS problem asks us to construct…