Improved upper bounds on all maximal \(\alpha\)-gapped repeats and palindromes

DOI10.1016/j.tcs.2018.06.033zbMath1495.68186arXiv1802.10355OpenAlexW2964070151MaRDI QIDQ1625598

Dominik Köppl, Tomohiro I.

Publication date: 29 November 2018

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

repetitionscombinatorics on wordsgapped palindromesgapped repeats

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Related Items (3)

The undirected repetition threshold and undirected pattern avoidance ⋮ Efficient computation of longest single-arm-gapped palindromes in a string ⋮ Efficient representation and counting of antipower factors in words

Uses Software

• MUMMER
• REPuter

Cites Work

• Unnamed Item
• Unnamed Item
• Extracting powers and periods in a word from its runs structure
• Counting distinct palindromes in a word in linear time
• Searching for gapped palindromes
• Searching of gapped repeats and subrepetitions in a word
• Tighter bounds and optimal algorithms for all maximal \(\alpha\)-gapped repeats and palindromes. Finding all maximal \(\alpha\)-gapped repeats and palindromes in optimal worst case time on integer alphabets
• On the number of gapped repeats with arbitrary gap
• Optimal Bounds for Computing $$\alpha $$ α -gapped Repeats
• Finding Gapped Palindromes Online
• A New Linear-Time ``On-Line Algorithm for Finding the Smallest Initial Palindrome of a String
• Algorithms on Strings, Trees and Sequences
• Gapped Pattern Statistics
• Uniqueness Theorems for Periodic Functions
• The “Runs” Theorem

This page was built for publication: Improved upper bounds on all maximal \(\alpha\)-gapped repeats and palindromes