Palindromic trees for a sliding window and its applications

DOI10.1016/J.IPL.2021.106174MaRDI QIDQ2234804zbMATH OpenOpenAlexFDO

Authors Takuya Mieno, Kiichi Watanabe, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

Publication date 19 October 2021

Published in Information Processing Letters (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2006.02134

zbMATH Keywords

data structuresstring algorithmspalindromessliding window

Mathematics Subject Classification ID

Data structures (68P05) Combinatorics on words (68R15) Algorithms on strings (68W32)

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 $sigma$ and is given in an online manner, then the palindromic tree of $S$ can be constructed in $O(nlogsigma)$ 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\mathrm{..}j]$ over $S$, where $1leqj-i+1leqd$. The first version works in $O(nlogsigm{a}^{\prime })$ time with $O(d)$ space where $sigm{a}^{\prime }leqd$ is the maximum number of distinct characters in the windows, and the second one works in $O(n+dsigma)$ time with $(d+2)sigma+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.

Recommendations

• Sliding suffix tree
• Tight bound for the number of distinct palindromes in a tree
• Counting palindromes in substrings

Cites work

• scientific article; zbMATH DE number 1024080 (Why is no real title available?)
• A New Linear-Time ``On-Line Algorithm for Finding the Smallest Initial Palindrome of a String
• A subquadratic algorithm for minimum palindromic factorization
• A universal algorithm for sequential data compression
• Absent words in a sliding window with applications
• Algorithms and combinatorial properties on shortest unique palindromic substrings
• Algorithms on Strings, Trees and Sequences
• Computing DAWGs and minimal absent words in linear time for integer alphabets
• Counting distinct palindromes in a word in linear time
• Diverse Palindromic Factorization is NP-Complete
• Episturmian words and some constructions of de Luca and Rauzy
• Fast algorithms for the shortest unique palindromic substring problem on run-length encoded strings
• Minimal Unique Substrings and Minimal Absent Words in a Sliding Window
• Minimum unique substrings and maximum repeats
• On-line construction of suffix trees
• Palindromic richness
• Using minimal absent words to build phylogeny
• Words and forbidden factors

Cited in

(4)

• Tight bound for the number of distinct palindromes in a tree
• Shortest unique palindromic substring queries in semi-dynamic settings
• Minimal unique palindromic substrings after single-character substitution
• Data structures for computing unique palindromes in static and non-static strings

Describes a project that uses

Uses Software

• EERTREE

This page was built for publication: Palindromic trees for a sliding window and its applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2234804)