106 citations · 239 across the 67 of their papers we have counts for
6 papers · 1 filter
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…
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…
Computing NP-hard Repetitiveness Measures via MAX-SAT
Hideo Bannai, Keisuke Goto, Masakazu Ishihata +3
Repetitiveness measures reveal profound characteristics of datasets, and give rise to compressed data structures and algorithms working in compressed space. Alas, the computation o…
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…
Longest (Sub-)Periodic Subsequence
Hideo Bannai, Tomohiro I, Dominik Köppl
We present an algorithm computing the longest periodic subsequence of a string of length in time with words of space. We obtain improvements when restricting…
Computing Longest (Common) Lyndon Subsequences
Hideo Bannai, Tomohiro I, Tomasz Kociumaka +2
Given a string with length whose characters are drawn from an ordered alphabet of size , its longest Lyndon subsequence is a longest subsequence of that is a Lyndon…