Kiichi Watanabe

dblp:238/0109 · DBLP profile ↗
← Back
3ranked-venue papers
2as first author
1since 2021 · last 2022
—ORCID · none

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 3 · 2 first-author · 1 since 2021Databases, data management, data science and information retrieval · 1 · 1 since 2021
YearPublicationVenuePosition
2022 Palindromic trees for a sliding window and its applications
abstract
The palindromic tree (a.k.a. eertree) for a string S of length n is a tree-like data structure that represents the set of all distinct palindromic substrings of S, using O(n) space [Rubinchik and Shur, 2018]. It is known that, when S is over an alphabet of size σ and is given in an online manner, then the palindromic tree of S can be constructed in O(nlog⁡σ) time with O(n) space. In this paper, we consider the sliding window version of the problem: For a sliding window of length at most d, we present two versions of an algorithm which maintains the palindromic tree of size O(d) for every sliding window S[i..j] over S, where 1≤j−i+1≤d. The first version works in O(nlog⁡σ′) time with O(d) space where σ′≤d is the maximum number of distinct characters in the windows, and the second one works in O(n+dσ) time with (d+2)σ+O(d) space. We also show how our algorithms can be applied to efficient computation of minimal unique palindromic substrings (MUPS) and minimal absent palindromic words (MAPW) for a sliding window.
Takuya Mieno, Kiichi Watanabe, Yuto Nakashima 0001, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda
Inf. Process. Lett.2
2020 Fast Algorithms for the Shortest Unique Palindromic Substring Problem on Run-Length Encoded Strings
Kiichi Watanabe, Yuto Nakashima 0001, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda
Theory Comput. Syst.1
2019 Shortest Unique Palindromic Substring Queries on Run-Length Encoded Strings
Kiichi Watanabe, Yuto Nakashima 0001, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda
IWOCA1