Algorithms and combinatorial properties on shortest unique palindromic substrings

DOI10.1016/j.jda.2018.11.009zbMath1412.68310OpenAlexW2901542900WikidataQ128949387 ScholiaQ128949387MaRDI QIDQ1711666

Yuto Nakashima, Takuya Mieno, Masayuki Takeda, Hideo Bannai, Hiroe Inoue, Shunsuke Inenaga

Publication date: 18 January 2019

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2018.11.009

zbMATH Keywords

palindromerich wordstring algorithmshortest unique substring (SUS)

Mathematics Subject Classification ID

Combinatorics on words (68R15) Algorithms on strings (68W32)

Related Items (5)

Minimal unique palindromic substrings after single-character substitution ⋮ Shortest unique palindromic substring queries in semi-dynamic settings ⋮ Data structures for computing unique palindromes in static and non-static strings ⋮ Palindromic trees for a sliding window and its applications ⋮ Fast algorithms for the shortest unique palindromic substring problem on run-length encoded strings

Uses Software

• EERTREE

Cites Work

• Unnamed Item
• Unnamed Item
• A subquadratic algorithm for minimum palindromic factorization
• Counting distinct palindromes in a word in linear time
• Computing longest previous factor in linear time and applications
• Palindromic richness
• EERTREE: an efficient data structure for processing palindromes in strings
• In-place algorithms for exact and approximate shortest unique substring problems
• Constructing suffix arrays in linear time
• Space efficient linear time construction of suffix arrays
• Shortest Unique Substrings Queries in Optimal Time
• Diverse Palindromic Factorization Is NP-complete
• Linear work suffix array construction
• A New Linear-Time ``On-Line Algorithm for Finding the Smallest Initial Palindrome of a String
• Shortest Unique Substring Queries on Run-Length Encoded Strings
• Counting Palindromes in Substrings
• Computing Palindromic Factorizations and Palindromic Covers On-line
• Shortest Unique Substring Query Revisited
• Episturmian words and some constructions of de Luca and Rauzy

This page was built for publication: Algorithms and combinatorial properties on shortest unique palindromic substrings