research
∙
07/05/2023
Linear-time computation of generalized minimal absent words for multiple strings
A string w is called a minimal absent word (MAW) for a string S if w doe...
share
research
∙
07/04/2023
Sliding suffix trees simplified
Sliding suffix trees (Fiala Greene, 1989) for an input text T over a...
research
∙
11/08/2022
Computing palindromes on a trie in linear time
A trie 𝒯 is a rooted tree such that each edge is labeled by a single cha...
research
∙
10/05/2022
Computing maximal generalized palindromes
Palindromes are popular and important objects in textual data processing...
research
∙
10/05/2022
Internal Longest Palindrome Queries in Optimal Time
Palindromes are strings that read the same forward and backward. Problem...
research
∙
07/09/2022
Online algorithms for finding distinct substrings with length and multiple prefix and suffix conditions
Let two static sequences of strings P and S, representing prefix and suf...
research
∙
04/15/2022
Shortest Unique Palindromic Substring Queries in Semi-dynamic Settings
A palindromic substring T[i.. j] of a string T is said to be a shortest ...
research
∙
02/28/2022
Minimal Absent Words on Run-Length Encoded Strings
A string w is called a minimal absent word (MAW) for another string T if...
research
∙
02/17/2022
RePair Grammars are the Smallest Grammars for Fibonacci Words
Grammar-based compression is a loss-less data compression scheme that re...
research
∙
02/09/2022
Cartesian Tree Subsequence Matching
Park et al. [TCS 2020] observed that the similarity between two (numeric...
research
∙
06/02/2021
On the approximation ratio of LZ-End to LZ77
A family of Lempel-Ziv factorizations is a well-studied string structure...
research
∙
05/25/2021
Minimal unique palindromic substrings after single-character substitution
A palindrome is a string that reads the same forward and backward. A pal...
research
∙
05/18/2021
Combinatorics of minimal absent words for a sliding window
A string w is called a minimal absent word (MAW) for another string T if...
research
∙
04/19/2021
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...
research
∙
07/16/2020
String Sanitization Under Edit Distance: Improved and Generalized
Let W be a string of length n over an alphabet Σ, k be a positive intege...
research
∙
06/24/2020
Lyndon Words, the Three Squares Lemma, and Primitive Squares
We revisit the so-called "Three Squares Lemma" by Crochemore and Rytter ...
research
∙
06/03/2020
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...
research
∙
09/06/2019
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...
research
∙
05/30/2019