
Grammar Index By Induced Suffix Sorting
Pattern matching is the most central task for text indices. Most recent ...
read it

Combinatorics of minimal absent words for a sliding window
A string w is called a minimal absent word (MAW) for another string T if...
read it

A Separation of γ and b via Thue–Morse Words
We prove that for n≥ 2, the size b(t_n) of the smallest bidirectional sc...
read it

Compressed Communication Complexity of Hamming Distance
We consider the communication complexity of the Hamming distance of two ...
read it

The Parameterized Suffix Tray
Let Σ and Π be disjoint alphabets, respectively called the static alphab...
read it

Lyndon Words, the Three Squares Lemma, and Primitive Squares
We revisit the socalled "Three Squares Lemma" by Crochemore and Rytter ...
read it

Computing Palindromic Trees for a Sliding Window and Its Applications
The palindromic tree (a.k.a. eertree) for a string S of length n is a tr...
read it

Longest Square Subsequence Problem Revisited
The longest square subsequence (LSS) problem consists of computing a lon...
read it

On repetitiveness measures of ThueMorse words
We show that the size γ(t_n) of the smallest string attractor of the nth...
read it

Towards Efficient Interactive Computation of Dynamic Time Warping Distance
The dynamic time warping (DTW) is a widelyused method that allows us to...
read it

Grammarcompressed Selfindex with Lyndon Words
We introduce a new class of straightline programs (SLPs), named the Lyn...
read it

Detecting k(Sub)Cadences and Equidistant Subsequence Occurrences
The equidistant subsequence pattern matching problem is considered. Give...
read it

DAWGs for parameterized matching: online construction and related indexing structures
Two strings x and y over Σ∪Π of equal length are said to parameterized m...
read it

Faster STRECLCS Computation
The longest common subsequence (LCS) problem is a central problem in str...
read it

Constructing the Bijective BWT
The BurrowsWheeler transform (BWT) is a permutation whose applications ...
read it

Minimal Unique Substrings and Minimal Absent Words in a Sliding Window
A substring u of a string T is called a minimal unique substring (MUS) o...
read it

The smallest grammar problem revisited
In a seminal paper of Charikar et al. on the smallest grammar problem, t...
read it

On Longest Common Property Preserved Substring Queries
We revisit the problem of longest common property preserving substring q...
read it

Direct Linear Time Construction of Parameterized Suffix and LCP Arrays for Constant Alphabets
We present the first worstcase linear time algorithm that directly comp...
read it

Compact Data Structures for Shortest Unique Substring Queries
Given a string T of length n, a substring u = T[i.. j] of T is called a ...
read it

OrderPreserving Pattern Matching Indeterminate Strings
Given an indeterminate string pattern p and an indeterminate string text...
read it

Dynamic Packed Compact Tries Revisited
Given a dynamic set K of k strings of total length n whose characters ar...
read it

Shortest Unique Palindromic Substring Queries on RunLength Encoded Strings
For a string S, a palindromic substring S[i..j] is said to be a shortest...
read it

The Parameterized Position Heap of a Trie
Let Σ and Π be disjoint alphabets of respective size σ and π. Two string...
read it

Faster queries for longest substring palindrome after block edit
Palindromes are important objects in strings which have been extensively...
read it

Computing runs on a trie
A maximal repeat, or run, in a string, is a periodically maximal substri...
read it

MRRePair: Grammar Compression based on Maximal Repeats
We analyze the grammar generation algorithm of the RePair compression al...
read it

Righttoleft online construction of parameterized position heaps
Two strings of equal length are said to parameterized match if there is ...
read it

O(n n)time text compression by LZstyle longest first substitution
Mauer et al. [A LempelZivstyle Compression Method for Repetitive Texts...
read it

Block Palindromes: A New Generalization of Palindromes
We propose a new generalization of palindromes and gapped palindromes ca...
read it

Online LZ77 Parsing and Matching Statistics with RLBWTs
LempelZiv 1977 (LZ77) parsing, matching statistics and the BurrowsWhee...
read it
Hideo Bannai
is this you? claim profile