106 citations · 249 across the 101 of their papers we have counts for
10 papers · 1 filter
A hardness result and new algorithm for the longest common palindromic subsequence problem
Shunsuke Inenaga, Heikki Hyyrö
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 betwe…
Computing All Distinct Squares in Linear Time for Integer Alphabets
Hideo Bannai, Shunsuke Inenaga, Dominik Köppl
Given a string on an integer alphabet, we present an algorithm that computes the set of all distinct squares belonging to this string in time linear to the string length. As an app…
Tight bounds on the maximum number of shortest unique substrings
Takuya Mieno, Shunsuke Inenaga, Hideo Bannai +1
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 ev…
Longest Common Subsequence in at Least Length Order-Isomorphic Substrings
Yohei Ueki, Diptarama, Masatoshi Kurihara +6
We consider the longest common subsequence (LCS) problem with the restriction that the common subsequence is required to consist of at least length substrings. First, we show a…
Efficient computation of longest single-arm-gapped palindromes in a string
Shintaro Narisada, Diptarama Hendrian, Kazuyuki Narisawa +2
In this paper, we introduce new types of approximate palindromes called single-arm-gapped palindromes (shortly SAGPs). A SAGP contains a gap in either its left or right arm, which…
Shortest unique palindromic substring queries in optimal time
Yuto Nakashima, Hiroe Inoue, Takuya Mieno +3
A palindrome is a string that reads the same forward and backward. A palindromic substring of a string is called a shortest unique palindromic substring () f…