Q1702853
type: Item
instance of: scholarly article
title: 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
zbMATH Open document ID: 1386.68120
author: Paweł Gawrychowski
author: Tomohiro I
author: Shunsuke Inenaga
author: Dominik Köppl
author: Florin Manea
published in: Theory of Computing Systems
publication date: 2018-03-01T00:00:00Z
Mathematics Subject Classification ID: 68R15
Mathematics Subject Classification ID: 68W32
zbMATH DE Number: 6845594
zbMATH Keywords: combinatorics on words
zbMATH Keywords: counting algorithms
MaRDI profile type: Publication
full work available at URL: s00224-017-9794-5
OpenAlex ID: W2746968256
cites work: Computing maximal-exponent factors in an overlap-free word
cites work: The “Runs” Theorem
cites work: Q3024804
cites work: Usefulness of the Karp-Miller-Rosenberg algorithm in parallel computations on strings and arrays
cites work: Computing longest previous non-overlapping factors
cites work: Efficient Algorithms for Two Extensions of LPF Table: The Power of Suffix Arrays
cites work: Optimal Bounds for Computing $$\alpha $$ α -gapped Repeats
cites work: Longest Gapped Repeats and Palindromes
cites work: Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays
cites work: Longest $$\alpha $$-Gapped Repeat and Palindrome
cites work: Finding Pseudo-Repetitions
cites work: Testing Generalised Freeness of Words
cites work: Efficiently Finding All Maximal alpha-gapped Repeats
cites work: Algorithms on Strings, Trees and Sequences
cites work: Linear work suffix array construction
cites work: Searching for gapped palindromes
cites work: Searching of Gapped Repeats and Subrepetitions in a Word
cites work: A New Linear-Time ``On-Line'' Algorithm for Finding the Smallest Initial Palindrome of a String
cites work: Making deterministic signatures quickly
cites work: A Faster Algorithm for Computing Maximal $$\alpha $$-gapped Repeats in a String
DOI: 10.1007/S00224-017-9794-5
Recommended article: Improved upper bounds on all maximal \(\alpha\)-gapped repeats and palindromes
Recommended article: A Faster Algorithm for Computing Maximal $$\alpha $$-gapped Repeats in a String
Recommended article: Optimal bounds for computing \({\alpha}\)-gapped repeats
Recommended article: Optimal Bounds for Computing $$\alpha $$ α -gapped Repeats
Recommended article: Efficiently Finding All Maximal alpha-gapped Repeats
Recommended article: Almost linear time computation of maximal repetitions in run length encoded strings
Recommended article: Longest $$\alpha $$-Gapped Repeat and Palindrome
Recommended article: Alphabet-independent algorithms for finding context-sensitive repeats in linear time
label: 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
description: scientific article; zbMATH DE number 6845594