Shunsuke Inenaga
6 papers in the PaperMetrix corpus
Papers by this author
-
Tight Bounds on the Maximum Number of Shortest Unique Substrings
2017 · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics)
A substring Q of a string S is called a shortest unique substring (SUS) for interval [s,t] in S, if Q occurs exactly once in S, this occurrence of Q contains interval [s,t], and every …
-
A hardness result and new algorithm for the longest common palindromic subsequence problem
2016 · arXiv (Cornell University)
The 2-LCPS problem, first introduced by Chowdhury et al. [Fundam. Inform., 129(4):329-340, 2014], asks one to compute (the length of) a longest palindromic common subsequence between two given strings $A$ and $B$. We show that …
-
Detecting $k$-(Sub-)Cadences and Equidistant Subsequence Occurrences
2020 · arXiv (Cornell University)
The equidistant subsequence pattern matching problem is considered. Given a pattern string $P$ and a text string $T$, we say that $P$ is an \emph{equidistant subsequence} of $T$ if $P$ is a subsequence of the …
-
Linear Time Online Algorithms for Constructing Linear-size Suffix Trie
2023 · arXiv (Cornell University)
The suffix trees are fundamental data structures for various kinds of string processing. The suffix tree of a text string $T$ of length $n$ has $O(n)$ nodes and edges, and the string label of each …
-
Subsequence Matching and LCS under Cartesian-Tree Equivalence
2024 · arXiv (Cornell University)
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 model that allows for capturing similarities of numerical …
-
On the sensitivity of CDAWG-grammars
2025 · arXiv (Cornell University)
The compact directed acyclic word graph (CDAWG) [Blumer et al. 1987] of a string is the minimal compact automaton that recognizes all the suffixes of the string. CDAWGs can be used for various string tasks …