Palindromic trees for a sliding window and its applications

DOI10.1016/J.IPL.2021.106174zbMATH Open1472.68225arXiv2006.02134OpenAlexW3187333287MaRDI QIDQ2234804FDOQ2234804

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)

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.

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

Recommendations

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

zbMATH Keywords

data structuresstring algorithmspalindromessliding window

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (4)

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

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)