Algorithms for anti-powers in strings

DOI10.1016/J.IPL.2018.05.003MaRDI QIDQ1641162zbMATH OpenOpenAlexFDO

Authors Golnaz Badkobeh, Gabriele Fici, Simon J. Puglisi

Publication date 15 June 2018

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

Full work available at URL https://arxiv.org/abs/1805.10042, http://hdl.handle.net/10138/308352

zbMATH Keywords

algorithmscombinatorics on wordsanti-periodsanti-powers

Mathematics Subject Classification ID

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

Abstract: A string $S[1,n]$ is a power (or tandem repeat) of order $k$ and period $n/k$ if it can decomposed into $k$ consecutive equal-length blocks of letters. Powers and periods are fundamental to string processing, and algorithms for their efficient computation have wide application and are heavily studied. Recently, Fici et al. (Proc. ICALP 2016) defined an {em anti-power} of order $k$ to be a string composed of $k$ pairwise-distinct blocks of the same length ($n/k$, called {em anti-period}). Anti-powers are a natural converse to powers, and are objects of combinatorial interest in their own right. In this paper we initiate the algorithmic study of anti-powers. Given a string $S$, we describe an optimal algorithm for locating all substrings of $S$ that are anti-powers of a specified order. The optimality of the algorithm follows form a combinatorial lemma that provides a lower bound on the number of distinct anti-powers of a given order: we prove that a string of length $n$ can contain $Theta(n^2/k)$ distinct anti-powers of order $k$.

Recommendations

• Anti-powers in infinite words
• Anti-powers in infinite words
• New simple efficient algorithms computing powers and runs in strings

Cites work

• Anti-power prefixes of the Thue-Morse word
• Anti-powers in infinite words
• Anti-powers in infinite words
• Repetitions in strings: algorithms and combinatorics
• Text redundancies
• Weighted ancestors in suffix trees

Cited in

(9)

• Computing the Antiperiod(s) of a String
• Anti-powers in infinite words
• Algebraic string operations
• Finding the Anticover of a String
• On anti-powers in aperiodic recurrent words
• Anti-power \(j\)-fixes of the Thue-Morse word
• NUMBER OF OCCURRENCES OF POWERS IN STRINGS
• On string replacement exponentiation
• Online algorithms on antipowers and antiperiods

This page was built for publication: Algorithms for anti-powers in strings

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