1 citations · 2 across the 6 of their papers we have counts for
5 papers · 1 filter
String Matching in (Block) Graphs: A Full Classification by Walk Length
Sebastian Angrick, Ben Bals, Paweł Gawrychowski +2
We consider directed graphs in which the nodes are labeled with strings. A walk in such a graph naturally corresponds to the concatenation of the visited nodes' labels. These graph…
Simple Linear-time Repetition Factorization
Yuki Yonemoto, Shunsuke Inenaga
A factorization of a string of length is called a repetition factorization of if is a repetition, i.e., is a form of , where i…
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…
Faster Space-Efficient STR-IC-LCS Computation
Yuki Yonemoto, Yuto Nakashima, Shunsuke Inenaga +1
One of the most fundamental method for comparing two given strings and is the longest common subsequence (LCS), where the task is to find (the length) of an LCS of and…